Pith. sign in

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 →

arxiv 1908.04003 v1 pith:JUFXXDZI submitted 2019-08-12 cs.LG cs.SIstat.ML

classification cs.LGcs.SIstat.ML
keywords graphautoencoderrandomwalkregularizationskipgramnodeclusteringlinkpredictionunsupervisedembeddingsvariationalwithrestart
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Graph autoencoders embed nodes by reconstructing the adjacency matrix, but the reconstruction loss alone does not constrain the latent space or force embeddings to encode the local structure of the network. This paper proposes adding a second, skipgram-style objective: for nodes visited by a random walk with restart, the encoder's embedding of a center node must predict nearby context nodes in the walk. The authors report that this random-walk regularization improves unsupervised node clustering on Cora, Citeseer, and PubMed, with relative gains up to 7.5% over the strongest baseline and larger relative gains over DeepWalk, while keeping link-prediction performance at par with strong baselines. If correct, the result matters because it is a simple, label-free modification to an existing architecture that improves embeddings without imposing a Gaussian prior or an adversarial discriminator.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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)
  1. [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.
  2. [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.
  3. [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.
  4. [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)
  1. [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.
  2. [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).
  3. [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.
  4. [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.
  5. [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

0 steps flagged · score 0.0 of 10

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 4 free parameters · 3 assumptions · 0 invented entities

No new entities; the method adds a training objective, not a new physical or mathematical object. The free parameters are hyperparameters tuned on validation, and the axioms are standard modeling assumptions.

free parameters (4)
  • window size = 30 or 20 depending on dataset
    Best value chosen on validation set; influences context span in skipgram. Reported in Section 6.3.
  • walk length = 30 or 20 depending on dataset
    Best value chosen on validation set; controls context horizon. Reported in Section 6.3.
  • number of walks = 50
    Set after validation; number of sampled vertices per epoch. Reported in Section 6.3.
  • restart probability alpha = not reported
    Algorithm 1 uses alpha but the paper never reports the value used in experiments.
assumptions (3)
  • domain assumption Random walk context prediction is a useful auxiliary objective for node clustering and link prediction.
    Section 4.4 states this without derivation; the paper treats it as a design choice.
  • domain assumption The 5% validation edge split is sufficient for hyperparameter tuning without leaking test information.
    Section 6.1 describes the split but does not check for overfitting.
  • standard math GCN encoder and inner product decoder retain their properties when trained with the additional skipgram loss.
    Used in Sections 4.1 to 4.4; no proof of convergence is given.

how reviews work

0 comments
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

Figures reproduced from arXiv: 1908.04003 by the authors.

Figure 1
Figure 1. Node embeddings learned by two different architectures. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Random Walk Regularized Graph Autoencoder. Top half of the network corresponds to the Graph Auto-Encoder. Bottom half [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Forward and backward propagation in order for training [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Visualization using node embeddings generated by different hyperparameters using RWR-GAE on Cora. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Aggregation-aware MLP: An Unsupervised Approach for Graph Message-passing

    cs.LG 2025-07 conditional novelty 4.0 of 10

    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

20 extracted references · 15 canonical work pages · cited by 1 Pith paper

  1. [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,

  2. [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,

  3. [8]

    Variational graph auto-encoders

    [Kipf and Welling, 2016b] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308,

  4. [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,

  5. [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,

  6. [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,

  7. [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,

  8. [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,

Show all 20 references
  1. [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

  2. [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,

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

  4. [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,

  5. [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,

  6. [2011]

    Auto-encoding variational bayes

    [Kingma and Welling, 2013] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114,

  7. [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 ,

  8. [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,

  9. [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,

  10. [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...

  11. [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,

  12. [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,

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.