REVIEW 4 major objections 6 minor 12 references
Rethinking Link Prediction for Directed Graphs
T0 review · 4 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read The paper argues that directed link prediction needs dual embeddings, proves that the leading simple auto-encoder is secretly a GCN on a bipartite graph, and builds a spectral version, SDGAE, that tops a new seven-dataset benchmark.
desk verdict DirLinkBench and the DiGAE-to-bipartite observation are solid; Proposition 3.2 is false as stated and the expressiveness narrative needs rework. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Lemma 5.1 is the load-bearing identity: DiGAE's pair of directed convolutions over $\hat{A}$ and $\hat{A}^{\top}$ is the same as one GCN convolution on the undirected bipartite graph whose adjacency matrix is the block matrix $S(\hat{A})$ with off-diagonal blocks $\hat{A}$ and $\hat{A}^{\top}$, the self-loops in $\hat{A}$ serving to keep that bipartite graph connected. Lemma 5.2 transfers symmetric normalization to this block form, so $\tilde{A} = \hat{D}_{\mathrm{out}}^{-1/2}\,\hat{A}\,\hat{D}_{\mathrm{in}}^{-1/2}$ is exactly the symmetric normalization of $S(\hat{A})$. SDGAE replaces DiGAE's stacked nonlinear layers with a polynomial filter $\sum_{k=0}^{K} W^{(k)} S(\tilde{A})^{k}$, with $W^{(k)} = \mathrm{diag}(w_S^{(k)} I_n,\, w_T^{(k)} I_n)$, implemented iteratively as $S^{(k+1)} = \gamma_S^{(k)} \tilde{A} T^{(k)} + S^{(k)}$ and $T^{(k+1)} = \gamma_T^{(k)} \tilde{A}^{\top} S^{(k)} + T^{(k)}$; the learned $\gamma$ weights re-express the polynomial coefficients and decay at higher orders, which the paper interprets as an efficient convergence property. This machinery lets SDGAE approximate arbitrary spectral filters on directed graphs while keeping separate source and target channels.
What would settle it
Train a single-embedding two-layer MLP with the concatenation decoder $\mathrm{MLP}(h_u \| h_v)$ on the three-node directed ring graph with one-hot node features and balanced edge/non-edge labels; near-perfect separation of the three directed edges from their reverses would directly contradict Proposition 3.2 as stated and would undercut the paper's claim that dual embeddings are required for directed reconstruction.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that a directed graph can be learned through its source–target symmetry: the graph convolution of DiGAE, written as one propagation over $\hat{A}$ and one over $\hat{A}^{\top}$, is indistinguishable from a single GCN convolution on the $2n$-node undirected bipartite graph whose adjacency matrix is the block matrix $S(\hat{A})$ with off-diagonal blocks $\hat{A}$ and $\hat{A}^{\top}$. The paper claims this identity explains why a simple auto-encoder outperforms elaborate directed GNNs under fair evaluation, and that it opens a spectral route: SDGAE learns arbitrary graph filters by polynomial approximation on $S(\tilde{A})$, where $\tilde{A} = \hat{D}_{\mathrm{out}}^{-1/2}\hat{A}\hat{D}_{\mathrm{in}}^{-1/2}$, with separate polynomial coefficients for source and target embeddings. On DirLinkBench, SDGAE achieves the best average rank (1.43) under Hits@100, wins on four of seven datasets, and ranks in the top two across all seven evaluation metrics, while also preserving in- and out-degree distributions better than DiGAE.
Load-bearing premise
The load-bearing premise is the expressiveness hierarchy of Proposition 3.2, whose proof treats the MLP decoder as the linear score $\sigma(h_1 w_1 + h_2 w_2)$ and asserts without proof that adding nonlinearities does not change the conclusion; if a general multi-layer MLP can separate a directed ring graph with expressive enough embeddings, the claim that single methods cannot reconstruct arbitrary directed graphs is not established as stated.
Editorial extensions
If this is right
- If SDGAE's benchmark result holds, Hits@100 and MRR should become the default metrics for directed link prediction, because accuracy, AUC, and AP saturate and rank many methods almost identically.
- DiGAE's equivalence to GCN on a bipartite graph means every undirected spectral filter design — Chebyshev, Bernstein, learned monomials — can be ported to directed graphs by applying it to $S(\tilde{A})$ with separate source and target coefficient blocks.
- SDGAE's gains come from filter flexibility rather than depth: increasing the polynomial order K improves SDGAE, whereas adding convolutional layers to DiGAE degrades it, so the field's focus on deeper directed GNNs is likely misplaced.
- Decoder and loss choices can outweigh the encoder: BCE beats CE consistently and MLP-style decoders beat inner products, which the paper uses to explain why complex-valued methods like MagNet and DUPLEX underperform.
- SDGAE propagates in time $O(2Kmd)$, linear in the number of edges, so the bipartite spectral approach remains feasible on graphs with hundreds of thousands of edges.
Reading between the lines
- Editorial inference: because the bipartite equivalence is a two-line algebraic identity, the same spectral toolbox could be applied to any directed graph representation, including weighted or signed adjacency matrices, simply by replacing $\hat{A}$ with the corresponding matrix.
- Editorial inference: if Proposition 3.2 fails for MLPs with hidden layers, the qualitative 'dual beats single' hierarchy may reduce to a statement about linear decoders; a controlled comparison of MLP($h_u \| h_v$) against source-target decoders at equal parameter counts on ring and chain graphs would settle whether the practical advice still holds.
- Editorial inference: the degree-distribution analysis suggests adding a distributional diagnostic — comparing reconstructed in/out degree sequences to the training graph — as a standard companion to Hits@100, and possibly a regularizer that penalizes degree-distribution mismatch.
- Editorial inference: since the benchmark pools multiple feature inputs and reports the best per method, the reported average could hide feature-specific failures; re-reporting per feature class would identify which gains are intrinsic to the model rather than to the chosen input.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper addresses directed link prediction from three angles: a theoretical framework for expressiveness of embedding types, a new benchmark DirLinkBench, and a new model SDGAE. The authors classify methods into single/dual embedding families, argue that dual methods are more expressive, identify flaws in existing evaluation setups, and propose a standardized benchmark with seven datasets, sixteen baselines, and seven metrics. They then show that DiGAE's convolution is equivalent to GCN on an undirected bipartite graph and propose SDGAE, a polynomial spectral auto-encoder that achieves the best average rank (1.43) on DirLinkBench under Hits@100. The paper also analyzes feature inputs, decoders, loss functions, degree distributions, and negative sampling.
Significance. The empirical contribution is substantial: DirLinkBench is a carefully designed resource with fixed splits, standardized feature options, and ranking-based metrics; the MLP-baseline finding and the label-leakage analysis are valuable correctives to prior evaluation practices. The bipartite-GCN interpretation of DiGAE is insightful, and the SDGAE design is simple, scalable, and empirically strong. However, the theoretical expressiveness hierarchy, advertised as a main contribution, is currently unsupported because Proposition 3.2 is false as stated for MLP decoders, and the 'arbitrary filter' claim for SDGAE is stronger than the parameterization warrants. These issues affect the conceptual framing rather than the validity of the benchmark experiments, so the paper is salvageable with a major revision.
major comments (4)
- [Section 3.1 and Appendix A.1] Proposition 3.2 is not established and, as stated, is false. The proof's contradiction argument models the MLP decoder as sigma(h_u w1 + h_v w2) (Eqs. 15-22), i.e., a single linear layer, and then states without proof that 'the same result holds even when nonlinearities are added.' That claim is incorrect: for any three distinct embeddings h1, h2, h3 in R^d, the six concatenated inputs [h_i; h_j] for ordered pairs (i,j) are distinct; a two-layer MLP with a hidden nonlinearity can realize any dichotomy on a finite set of distinct points, in particular the directed 3-cycle pattern (positive for 1->2, 2->3, 3->1 and negative for the three reverse pairs). Hence Proposition 3.2's conclusion that single methods 'fail for directed ring graphs' is false for the MLP decoder class defined in Table 2. The expressiveness hierarchy 'dual methods are more expressive' therefore lacks a valid proof. Please restrict the proposition to the linear decoder actually analyzed, or prove the MLP statement; if the latter cannot be done, the narrative in Section 3.1 and the 'contradicts the theoretical assumption' passage in Section 3.2 should be revised accordingly.
- [Section 5.2, Eqs. (9)-(14)] The claim that SDGAE 'can approximate arbitrary graph filters' is not supported by the parameterization. In Eq. (10), W^(k) = diag([w_S^(k) I_n, w_T^(k) I_n]) yields a filter of the form U_S diag(p_S(lambda_i), p_T(lambda_i)) U_S^T with two polynomials p_S and p_T, not an arbitrary filter h(S(A~)). Furthermore, the iterative implementation in Eqs. (11)-(12) restricts the polynomial coefficients to sums and products of the scalar gamma's; for example, for K=2, w_S^(2)=gamma_S^(1) gamma_T^(0), so the achievable coefficient set is a low-dimensional curved family rather than the full space of degree-K polynomials, and with the observed gamma in (0,1) the learned filters are positive and decaying. Please state the exact filter class and either use a parameterization that spans the full polynomial space (e.g., direct coefficient learning as in Eq. (9)) or soften the 'arbitrary filter' claim.
- [Section 4.4 and Appendix B.2] The benchmark reports 'the best mean result across different combinations of feature inputs, loss functions, and decoders' for each method. It is not stated whether this selection is made on the validation splits or on the test splits. If test-based selection is used, all reported numbers, including SDGAE's SOTA average rank in Table 8, are optimistically biased and the comparisons are not uniform. The manuscript should specify unambiguously that every configuration (features, loss, decoder, hyperparameters) is chosen on validation data only, and ideally report the standard deviations across the 10 fixed splits for the selected configuration.
- [Section 3.2, Issue 1] The text says that MLP's strong performance on existing setups 'contradicts the theoretical assumption that dual methods are more expressive.' Since Proposition 3.2 is the only formal basis for that assumption and it is flawed as noted above, the contradiction is not meaningful as stated. The empirical observation is valuable, but the conceptual framing needs to be reconciled with the (corrected) theory, or the theoretical claim should be separated from the benchmark findings.
minor comments (6)
- [Section 3.2, Issue 1] The text refers to 'EF tasks' where 'EP tasks' is meant (see Table 4 and surrounding discussion).
- [Section 3.2, Issue 2 and Section 4.1] The method name 'LighDiC' is a typo for 'LightDiC'.
- [Appendix B.2] The typo 'DCN' should be 'DGCN', and 'DYHPR' should be 'DHYPR'.
- [Abstract and Section 1] The code link 'here' is a placeholder; provide a working URL.
- [Table 2] The decoder 'Direc(z_u, z_v)' for complex-valued methods is not defined in the text; define it or cite the exact DUPLEX formulation.
- [Appendix A.1] The proof refers to graphs (a) and (d) in Figure 3, but the figure caption describes bipartite representations; ensure the subfigure labels are visible and match the proof's references.
Circularity Check
No significant circularity: SDGAE's derivation is an algebraic equivalence, and its benchmark evaluation is against external data; the flawed Proposition 3.2 is a correctness issue, not a circular one.
full rationale
The paper's central derivations are self-contained. Lemma 5.1 is proven by direct substitution of the block matrix S(hat A) into DiGAE's convolutional equations (Appendix A.2), and Lemma 5.2 is an algebraic identity for the symmetric normalization; neither assumes its conclusion. SDGAE's polynomial-filter formulation is a standard spectral-GNN construction, and its state-of-the-art claim is an empirical result on DirLinkBench, which uses external real-world datasets with fixed splits and metrics rather than targets derived from the model itself. The benchmark, while introduced by the authors, compares 16 methods on shared data and therefore does not reduce the reported rankings to the model's own definitions. The paper contains self-citations (BernNet, ChebNetII, PyGSD) but these are used as background, baselines, or a heuristic explanation for coefficient initialization; none is invoked as an unverified premise that forces the main result. The concerning Proposition 3.2 is not circular: it is a (likely false) mathematical claim whose proof models the decoder as a single linear layer and asserts without proof that nonlinearities do not change the conclusion. A two-layer MLP can separate the directed 3-cycle, so the proposition is a correctness risk for the expressiveness narrative, but it is not equivalent to its inputs by construction, and it does not support the empirical SOTA or the DiGAE/SDGAE equivalence. Under the hard rules, a false or unproven claim is a correctness problem, not circularity, so the circularity score is 0.
Assumptions & free parameters
free parameters (3)
- Polynomial order K =
3, 4, or 5, chosen per dataset (Table 12)
- Polynomial coefficient parameterization gamma =
initialized to 1, learned; w(k) are products of gammas
- Hyperparameters (lr, wd, MLP layers) =
per dataset (Table 12) and per baseline
assumptions (3)
- standard math Polynomials can approximate arbitrary continuous spectral filters (Weierstrass/Stone approximation)
- domain assumption The 7 selected datasets represent the space of directed link prediction tasks
- ad hoc to paper The assertion that adding nonlinearities to the MLP does not change Proposition 3.2's failure case
Cite this review
Pith. "Pith review of Rethinking Link Prediction for Directed Graphs." pith.science (2026). https://pith.science/paper/3TNZ4G7W
@misc{pith2026250205724,
author = {Pith},
title = {Pith review of: Rethinking Link Prediction for Directed Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/3TNZ4G7W}},
note = {Machine review of arXiv:2502.05724}
}
read the original abstract
Link prediction for directed graphs is a crucial task with diverse real-world applications. Recent advances in embedding methods and Graph Neural Networks (GNNs) have shown promising improvements. However, these methods often lack a thorough analysis of their expressiveness and suffer from effective benchmarks for a fair evaluation. In this paper, we propose a unified framework to assess the expressiveness of existing methods, highlighting the impact of dual embeddings and decoder design on directed link prediction performance. To address limitations in current benchmark setups, we introduce DirLinkBench, a robust new benchmark with comprehensive coverage, standardized evaluation, and modular extensibility. The results on DirLinkBench show that current methods struggle to achieve strong performance, while DiGAE outperforms other baselines overall. We further revisit DiGAE theoretically, showing its graph convolution aligns with GCN on an undirected bipartite graph. Inspired by these insights, we propose a novel Spectral Directed Graph Auto-Encoder SDGAE that achieves state-of-the-art average performance on DirLinkBench. Finally, we analyze key factors influencing directed link prediction and highlight open challenges in this field.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[5]
Monti, F., Otness, K., and Bronstein, M. M. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225–228. IEEE,
work page 2018
-
[11]
ˆD−1/2 out 0 0 ˆD−1/2 in # 0 ˆA ˆA⊤ 0
(22) Adding these three inequalities (20), (21), and (22), results in 0 > 0, which is a contradiction and indicates that no embeddings h1, h2, h3 and weights w1, w2 exist that can satisfy these conditions. The same result holds even when nonlinearities are added to the MLP. Therefore, single methods with the decoder MLP(hu∥hv) fail to compute the probabil...
work page 2017
-
[64]
This ensures that all methods have approximately the same number of learnable parameters, a common practice in many GNN benchmarks (Hu et al., 2020; Chien et al., 2021). Some models have exceptions. For example, DUPLEX uses three layers across all datasets in its official implementation; given its status as a recent advanced method, we search over layers ...
work page 2020
-
[2000]
Mernyei, P. and Cangea, C. Wiki-cs: A wikipedia-based benchmark for graph neural networks. arXiv preprint arXiv:2007.02901,
arXiv 2007
-
[2008]
Pitfalls of graph neural network evaluation
Shchur, O., Mumme, M., Bojchevski, A., and G¨unnemann, S. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018,
work page 2018
-
[2013]
A survey on spectral graph neural networks
Bo, D., Wang, X., Liu, Y ., Fang, Y ., Li, Y ., and Shi, C. A survey on spectral graph neural networks. arXiv preprint arXiv:2302.05631,
-
[2015]
Digraph inception convolutional networks
Tong, Z., Liang, Y ., Sun, C., Li, X., Rosenblum, D., and Lim, A. Digraph inception convolutional networks. NeurIPS, 33:17907–17918, 2020a. Tong, Z., Liang, Y ., Sun, C., Rosenblum, D. S., and Lim, A. Directed graph convolutional network. arXiv preprint arXiv:2004.13970, 2020b. Veliˇckovi´c, P., Cucurull, G., Casanova, A., Romero, A., Li`o, P., and Bengio...
arXiv 2004
-
[2016]
Fey, M. and Lenssen, J. E. Fast graph representation learning with pytorch geometric.arXiv preprint arXiv:1903.02428,
arXiv 1903
Show all 12 references
-
[2018]
Finding large balanced subgraphs in signed networks
Ordozgoiti, B., Matakos, A., and Gionis, A. Finding large balanced subgraphs in signed networks. In Proceedings of The Web Conference 2020, pp. 1378–1388,
2020
-
[2019]
Disentangling degree-related biases and interest for out-of-distribution generalized directed network embedding
Yoo, H., Lee, Y .-C., Shin, K., and Kim, S.-W. Disentangling degree-related biases and interest for out-of-distribution generalized directed network embedding. In Proceedings of the ACM Web Conference 2023, pp. 231–239,
2023
-
[2020]
Exploring the role of node diversity in directed graph representation learning
Huang, J., Mo, Y ., Hu, P., Shi, X., Yuan, S., Zhang, Z., and Zhu, X. Exploring the role of node diversity in directed graph representation learning. In IJCAI, pp. 2072–2080,
-
[2022]
Interpreting and unifying graph neural networks with an optimization framework
Zhu, M., Wang, X., Shi, C., Ji, H., and Cui, P. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pp. 1215–1226, 2021a. Zhu, S., Li, J., Peng, H., Wang, S., and He, L. Adversarial directed graph embedding...
2021
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.