REVIEW 4 major objections 5 minor 1 cited by
RWR-GAE: Random Walk Regularization for Graph Auto Encoders
T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Random-walk regularization lifts graph-autoencoder clustering accuracy by up to 7.5%.
desk verdict A plausible incremental regularizer for graph autoencoders, undermined by an unverified link prediction protocol and an abstract that overstates its own table. 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
The load-bearing mechanism is the joint objective that combines the graph autoencoder's reconstruction loss with a skipgram log-likelihood over random-walk-with-restart contexts. Random Walk with Restarts generates a context set for a sampled start node by repeatedly moving to a random neighbor or jumping back to the start; a skipgram layer then predicts each context node from the encoder's embedding of the center node. The gradient of this objective is routed to both the skipgram parameters and the encoder, so the latent vectors are pushed to be informative about local neighborhoods while the reconstruction loss keeps them useful for link prediction. This combination is what carries the reported clustering gains.
What would settle it
On Cora, rerun the released code with the same train/validation/test split, once with the test and validation edges explicitly zeroed out of the adjacency matrix before training and once with them left in; if the two runs give nearly identical AUC/AP, or if the reported numbers only appear when the held-out edges are visible, the link-prediction claim collapses.
Extended reading notes
Core claim
The central claim is that a graph autoencoder's latent node embeddings improve when the encoder is jointly trained to predict random-walk context nodes through a skipgram objective. Unlike an adversarial regularizer that pulls the latent distribution toward a Gaussian, the proposed regularizer adds no distributional prior; it supplies dense local supervision by maximizing the log-probability of nodes appearing near a start node in a random walk with restarts. The paper reports that this makes intra-cluster embeddings more evenly spread (intra-cluster distance 0.64 versus 0.99 for the plain autoencoder on Cora, measured as averaged distance to cluster centroids), and that the resulting embeddings improve clustering accuracy, NMI, F1, precision, and adjusted Rand index on all three datasets while matching baseline link prediction. The same regularization is applied to both the standard and variational graph autoencoders, yielding the RWR-GAE and RWR-VGAE variants.
Load-bearing premise
The link-prediction results assume the 10% test edges and 5% validation edges are removed from the adjacency matrix fed to the graph convolutional encoder during training; if those edges remain visible, the reported AUC and average-precision scores on held-out edges are not measuring prediction of unobserved links.
Editorial extensions
If this is right
- On Cora, random-walk regularized autoencoders improve clustering accuracy by 41.5% relative to DeepWalk and by 12.4% relative to the variational graph autoencoder; on Citeseer, RWR-GAE beats the adversarial regularizer by 7.5% in accuracy and 7.1% in F1 score.
- On PubMed, RWR-VGAE raises clustering accuracy to 0.736 and adjusted Rand index to 0.381, a relative ARI improvement of 18.3% over the plain graph autoencoder.
- The regularized embeddings have lower intra-cluster distance (0.64 versus 0.99 for GAE on Cora), which the paper links to an even intra-cluster spread and greater robustness at cluster boundaries.
- Training dynamics change: the encoder receives more gradient updates per pass, so the model reaches its best accuracy in about 100 epochs instead of 200, while link-prediction variance increases because of random-walk sampling.
- Both standard and variational graph autoencoders benefit, so the regularizer is a drop-in addition rather than a new architecture.
Reading between the lines
- A natural untested extension is to apply the same skipgram regularizer to graph autoencoders built on other encoder families (for example, inductive or attention-based encoders), since the regularizer only touches the encoder output and should transfer wherever local context matters.
- The restart probability in the random walk is a direct dial between local and global context; varying it and measuring clustering accuracy would reveal how much of the gain comes from short-range versus long-range neighborhoods, and whether an optimal setting exists per dataset.
- Replacing the inner-product decoder with a different link predictor while keeping the regularizer would test whether the clustering gains are tied to reconstruction or to the context objective itself.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proposes RWR-GAE and RWR-VGAE, which add a random-walk-with-restart skipgram objective to the training of graph autoencoders and variational graph autoencoders. The regularization objective encourages each node embedding to predict its context nodes, providing additional supervision beyond the reconstruction loss. The method is evaluated on unsupervised node clustering and link prediction for Cora, Citeseer, and PubMed, reporting improved clustering accuracy over several baselines and claiming state-of-the-art link prediction results.
Significance. If the experimental concerns are resolved, the regularization idea is a simple and plausible enhancement to graph autoencoders, and the clustering results on three standard citation networks suggest the approach is worth publishing. The paper provides a detailed algorithm description and makes concrete falsifiable claims against standard baselines. However, the current manuscript does not support the link prediction claim: Table 2 shows that adversarial baselines often outperform the proposed method, and the evaluation protocol for held-out edges is not fully specified. The clustering claims also lack statistical support.
major comments (4)
- [Section 6.1] Section 6.1 does not state whether the 5% validation and 10% test citation edges are removed from the adjacency matrix A used by the GCN encoder in Eq. (2) and the decoder in Eq. (5). Without this masking, the decoder can memorize held-out edges, so the link prediction AUC and AP values in Table 2 would not reflect generalization; the original VGAE protocol (Kipf and Welling 2016b) explicitly removes these edges. The authors must either state that they follow this protocol or rerun the experiments with proper masking.
- [Abstract and Section 7] The abstract's claim of 'state-of-the-art accuracy on the link prediction task' is contradicted by Table 2. For example, ARGE achieves higher AP than RWR-GAE on all three datasets (Cora 93.2 vs 92.7, Citeseer 93.0 vs 91.5, PubMed 97.1 vs 96.3) and higher AUC on PubMed (96.8 vs 96.2). Section 7 itself states that 'our proposed method performs at par with the existing baselines.' The abstract and contribution list should be revised to match the actual findings, or the evaluation should be reconsidered if the masking issue discussed above changes the results.
- [Tables 3-5] Tables 3, 4, and 5 report clustering metrics without standard deviations or significance tests, despite Table 2 showing that the RWR methods have high run-to-run variance (e.g., RWR-GAE Cora AUC 92.9 ± 0.3). Consequently, the claimed clustering improvements (e.g., Cora RWR-VGAE accuracy 0.685 vs ARVGE 0.638) may not be statistically significant; the authors should report mean ± standard deviation over multiple runs and/or a significance test.
- [Section 4.4 and Algorithm 2] Eq. (11) and Algorithm 2 define the regularization loss inconsistently. Eq. (11) writes LS = log p(µ_i | Z(v_i)) with µ_i ∈ W_{v_i}, whereas Algorithm 2 uses a negative log-likelihood L_vj = -log Pr(µ_k | Z(v_j)) and updates with ∇L_vj. Additionally, the text says the skipgram model has 'two embedding layers corresponding to the nodes and context nodes,' but Eq. (11) uses the encoder output Z(v_i); it is unclear whether separate context embeddings exist and how they are trained. Please clarify the exact objective and parameterization, since this is the central method of the paper.
minor comments (5)
- [Abstract] The code link (https://github.com/MysteryVaibhav/DW-GAE) points to a repository named DW-GAE rather than RWR-GAE; please update the link or clarify the relationship between the two names.
- [Throughout] There are several typos, e.g., 'datatset' in Section 6.1, 'Eu-toencoder' in Section 4.4, 'dimentation' and 'adjaceny' in Section 2, 'divergance' in Eq. (10), and 'Guassian' in Eq. (10).
- [Section 6.3] The hyperparameter values are not fully specified: 'window size to {30, 20} and walk length to {30, 20}' does not state which combination is used for which dataset or model.
- [Eq. (8) and Eq. (11)] The notation µ is overloaded: it denotes context nodes in Eq. (11) but the mean vector of the variational posterior in Eq. (8). Please use distinct symbols.
- [Figure 4] The caption sets 'number of walks = walk length = window size = {5, 20, 30}', which is inconsistent with the '50 walks' stated in Section 6.3; please clarify.
Circularity Check
No circularity: the random-walk regularization is an external training signal and all evaluations are against held-out or external targets.
full rationale
The paper's central claim is that adding a skipgram objective on Random Walk with Restarts (RWR) contexts regularizes graph-autoencoder embeddings. This regularization is an additional loss term (Eq. 11) computed from random walks over the input graph, which is independent of the downstream evaluation targets: node clustering uses K-means on the learned embeddings with ground-truth class labels, and link prediction uses held-out edges with AUC/AP metrics. The model is trained on the reconstruction loss (Eq. 6 or Eq. 10) plus the skipgram loss; neither loss incorporates the test cluster labels or the test edges. Hyperparameters for the random walk are chosen on a 5% validation split of edges, not fit to the test set. The paper cites Kipf & Welling, Pan et al., Perozzi et al., and others, but none of these are self-citations by the present authors, and no load-bearing argument reduces to a self-citation chain. The reader's flagged weaknesses (possible unmasked test edges during link prediction, the DW-GAE repository name, and the overstatement that link prediction is state-of-the-art when Table 2 shows otherwise) are validity or correctness concerns, not circularity: they do not show that any predicted quantity is equivalent to its inputs by construction. The derivation of the regularization from random-walk contexts and its evaluation against external labels and held-out edges is self-contained. Therefore no circular step is present.
Assumptions & free parameters
free parameters (4)
- window size =
30 or 20 depending on dataset
- walk length =
30 or 20 depending on dataset
- number of walks =
50
- restart probability alpha =
not reported
assumptions (3)
- domain assumption Random walk context prediction is a useful auxiliary objective for node clustering and link prediction.
- domain assumption The 5% validation edge split is sufficient for hyperparameter tuning without leaking test information.
- standard math GCN encoder and inner product decoder retain their properties when trained with the additional skipgram loss.
Cite this review
Pith. "Pith review of RWR-GAE: Random Walk Regularization for Graph Auto Encoders." pith.science (2026). https://pith.science/paper/JUFXXDZI
@misc{pith2026190804003,
author = {Pith},
title = {Pith review of: RWR-GAE: Random Walk Regularization for Graph Auto Encoders},
year = {2026},
howpublished = {\url{https://pith.science/paper/JUFXXDZI}},
note = {Machine review of arXiv:1908.04003}
}
read the original abstract
Node embeddings have become an ubiquitous technique for representing graph data in a low dimensional space. Graph autoencoders, as one of the widely adapted deep models, have been proposed to learn graph embeddings in an unsupervised way by minimizing the reconstruction error for the graph data. However, its reconstruction loss ignores the distribution of the latent representation, and thus leading to inferior embeddings. To mitigate this problem, we propose a random walk based method to regularize the representations learnt by the encoder. We show that the proposed novel enhancement beats the existing state-of-the-art models by a large margin (upto 7.5\%) for node clustering task, and achieves state-of-the-art accuracy on the link prediction task for three standard datasets, cora, citeseer and pubmed. Code available at https://github.com/MysteryVaibhav/DW-GAE.
Figures
Forward citations
Cited by 1 Pith paper
-
Aggregation-aware MLP: An Unsupervised Approach for Graph Message-passing
AMLP is a simple unsupervised framework that makes a single MLP adaptive to graph aggregation through a neighbor-consistency loss and a reconstructed graph, and it reports strong clustering and classification performance.
Reference graph
Works this paper leans on
-
[1]
Laplacian eigenmaps and spectral techniques for embedding and clustering
[Belkin and Niyogi, 2002] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pages 585–591,
work page 2002
-
[4]
node2vec: Scalable feature learning for networks
[Grover and Leskovec, 2016] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864. ACM,
work page 2016
-
[8]
Variational graph auto-encoders
[Kipf and Welling, 2016b] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308,
-
[9]
Efficient estimation of word representations in vector space
[Mikolov et al., 2013a] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781,
-
[10]
Automatic multimedia cross-modal correlation discovery
[Pan et al., 2004] Jia-Yu Pan, Hyung-Jeong Yang, Christos Faloutsos, and Pinar Duygulu. Automatic multimedia cross-modal correlation discovery. In Proceedings of the tenth ACM SIGKDD international conference on Knowl- edge discovery and data mining , pages 653–658. ACM,
work page 2004
-
[12]
Deepwalk: Online learning of social repre- sentations
[Perozzi et al., 2014] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD in- ternational conference on Knowledge discovery and data mining, pages 701–710. ACM,
work page 2014
-
[16]
Line: Large- scale information network embedding
[Tang et al., 2015] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. In Proceedings of the 24th international conference on world wide web , pages 1067–1077. International World Wide Web Confer- ences Steering Committee,
work page 2015
-
[18]
Mgae: Marginal- ized graph autoencoder for graph clustering
[Wang et al., 2017a] Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginal- ized graph autoencoder for graph clustering. In Proceed- ings of the 2017 ACM on Conference on Information and Knowledge Management, pages 889–898. ACM,
work page 2017
Show all 20 references
-
[20]
Network representa- tion learning with rich text information
[Yang et al., 2015] Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Chang. Network representa- tion learning with rich text information. In Twenty-Fourth International Joint Conference on Artificial Intelligence , 2015
2015
-
[2000]
Collective classification in network data
[Sen et al., 2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI magazine , 29(3):93,
2008
-
[2002]
A survey on network embedding
[Cui et al., 2018] Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey on network embedding. IEEE Transactions on Knowledge and Data Engineering,
2018
-
[2004]
Adver- sarially regularized graph autoencoder
[Pan et al., 2018] Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adver- sarially regularized graph autoencoder. arXiv preprint arXiv:1802.04407,
2018 arXiv
-
[2008]
Leveraging social media networks for classification
[Tang and Liu, 2011] Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery, 23(3):447–478,
2011
-
[2011]
Auto-encoding variational bayes
[Kingma and Welling, 2013] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114,
2013 arXiv
-
[2013]
Semi-supervised classification with graph con- volutional networks
[Kipf and Welling, 2016a] Thomas N Kipf and Max Welling. Semi-supervised classification with graph con- volutional networks. arXiv preprint arXiv:1609.02907 ,
-
[2014]
Nonlinear dimensionality reduction by locally lin- ear embedding
[Roweis and Saul, 2000] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally lin- ear embedding. science, 290(5500):2323–2326,
2000
-
[2015]
Acceler- ating t-sne using tree-based algorithms
[Van Der Maaten, 2014] Laurens Van Der Maaten. Acceler- ating t-sne using tree-based algorithms. The Journal of Machine Learning Research, 15(1):3221–3245,
2014
-
[2016]
It’s who you know: graph mining using recursive structural features
[Henderson et al., 2011] Keith Henderson, Brian Gallagher, Lei Li, Leman Akoglu, Tina Eliassi-Rad, Hanghang Tong, and Christos Faloutsos. It’s who you know: graph mining using recursive structural features. In Proceedings of the 17th ACM SIGKDD international conference on Know...
2011
-
[2017]
Robust multi-view spectral clustering via low-rank and sparse decomposition
[Xia et al., 2014] Rongkai Xia, Yan Pan, Lei Du, and Jian Yin. Robust multi-view spectral clustering via low-rank and sparse decomposition. In AAAI, pages 2149–2155,
2014
-
[2018]
Capturing edge attributes via network embedding
[Goyal et al., 2018] Palash Goyal, Homa Hosseinmardi, Emilio Ferrara, and Aram Galstyan. Capturing edge attributes via network embedding. arXiv preprint arXiv:1805.03280,
2018 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.