Pith. sign in

REVIEW 4 major objections 5 minor 21 references

Dynamic Graph Embedding Through Hub-aware Random Walks

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Hub-repelling random walks beat the standard baseline on 8 of 9 networks

desk verdict A simple, transparent extension of hub-aware random walks to dynamic graphs, but the empirical claim is weakened by tuning on the test metric and the abstract overstates downstream gains. read the letter →

arxiv 2505.17764 v2 pith:G2HP4FR2 submitted 2025-05-23 cs.SI

Aleksandar Tomčić , Miloš Savić , Dušan Simić , Miloš Radovanović This is my paper · ORCID
classification cs.SI MSC 68R1005C82
keywords dynamicgraphembeddingrandomwalkshubsdegreecentralityreconstructiondynnode2vectemporalnetworksrepresentationlearning
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

This paper claims that dynamic graph embeddings built from random walks are distorted by hub overrepresentation, and that explicitly biasing walk transitions according to node degree corrects the distortion. To test this, the authors introduce DeepHub, a random walk strategy that scores neighbors by degree centrality with optional inverse or logarithmic scaling, and compare it against dynnode2vec on nine real temporal networks. DeepHub achieves higher graph reconstruction F1 on eight of the nine networks and reduces the gap between hubs and non-hubs in several cases. The paper's central claim is that hub-awareness is an overlooked factor in dynamic graph embedding, and that a lightweight change to walk sampling can improve intrinsic embedding quality across diverse networks.

What carries the argument

The core mechanism is a degree-biased transition distribution inside the random walk, governed by three parameters: backtracking probability p, uniform-move probability u, and a degree-scoring mode (normal, inverse, log, or inverse-log). Rather than handling hubness as a post-hoc alignment step, the bias is injected at sampling time within the standard dynnode2vec incremental-update loop, so the walk itself produces contexts in which less-connected nodes are not drowned out by high-degree neighbors.

What would settle it

Run DeepHub and dynnode2vec with a fixed, pre-registered hyperparameter budget and evaluate on a held-out snapshot or a downstream task such as link prediction; if DeepHub no longer beats dynnode2vec on most networks, the hub-awareness advantage claimed here does not transfer beyond the tuning procedure.

Watch

Extended reading notes

Core claim

DeepHub modifies dynnode2vec's random walk sampling so that at each step, with probability p the walker backtracks to the previous node, with probability u it moves to a uniformly random neighbor, and otherwise it samples among neighbors with probabilities proportional to degree-based scores. The scores are either proportional to degree, or inversely proportional via 1 + max_deg - deg(n), optionally with a log transform, and in the configurations that worked best on the tested networks the walker avoids hubs. Across nine temporal networks, DeepHub's best-tuned F1 exceeds dynnode2vec's on eight of them, with relative improvements up to about 17.8 percent, and it lowers the hub versus non-hub F1 gap enough that a Mann-Whitney test can no longer reject equal distributions in three networks where dynnode2vec showed significant differences.

Load-bearing premise

The paper's central evidence is a comparison where the same F1 metric on the last snapshot is used both to pick hyperparameters and to report results, so the reported gains may partly reflect DeepHub's extra tuning freedom rather than hub awareness itself.

Editorial extensions

If this is right

  • DeepHub improves graph reconstruction F1 over dynnode2vec on 8 of 9 real temporal networks, with the largest gains appearing on networks where hubs were strongly overrepresented.
  • The best configurations consistently use inverse or inverse-log degree scaling, meaning walkers that avoid hubs produce higher-quality embeddings in these networks.
  • Hub-aware sampling makes hub and non-hub node embeddings more comparable, with the hub versus non-hub F1 gap no longer statistically significant in three networks where it was significant for the baseline.
  • Because DeepHub changes only the sampling strategy, it can be dropped into the incremental-update framework of dynnode2vec without altering the model architecture or the embedding update step.

Reading between the lines

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

  • A natural testable extension is to combine hub-aware sampling with local-intrinsic-dimensionality-based walk biases, since both target the same failure mode of standard walks.
  • The inverse-log scaling that won most networks suggests an optimal trade-off curve between exploration and hub avoidance; tuning that curve per network may yield further gains beyond the grid used here.
  • If hub-awareness improves reconstruction F1, it likely also helps downstream tasks such as link prediction and node classification, but the paper does not test those tasks, so that transfer remains an open inference.
Share X Bluesky LinkedIn Reddit HN

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 paper proposes DeepHub, a dynamic graph embedding method that augments the dynnode2vec sampling procedure with degree-based transition scoring. In addition to the return parameter p and a uniform-move probability u, DeepHub chooses among four degree transforms (normal, log, inverse, inverse-log) to bias walks toward or away from hubs. The authors evaluate DeepHub and the dynnode2vec baseline on nine real temporal networks using micro-averaged graph reconstruction F1 on the last snapshot, and they also analyze hub/non-hub F1 differences with Spearman correlations and Mann-Whitney U tests. They report that DeepHub outperforms dynnode2vec on eight of nine datasets, and that the best per-dataset transform is always inverse or inverse-log, which they interpret as evidence that avoiding hubs improves embeddings.

Significance. The idea of making dynamic random-walk embeddings structurally aware of hubs is reasonable and not well explored, and the method is simple enough to be usable. The paper's strengths include a systematic comparison across nine publicly available datasets, a careful hub/non-hub fairness analysis, and explicit reporting of selected hyperparameters. However, the main empirical claim currently rests on an evaluation protocol in which the same last-snapshot reconstruction F1 is used both to select hyperparameters and to report final scores, and DeepHub has more tunable axes than the baseline. The significance of the paper will rise or fall on whether the 8-of-9 advantage survives an independent held-out evaluation.

major comments (4)
  1. [Section 4, baseline tuning paragraph; Tables 2 and 5] The evaluation protocol tunes both dynnode2vec and DeepHub by maximizing the last-snapshot graph reconstruction F1 and then reports that same F1 as the outcome. Because DeepHub has additional hyperparameter axes (the uniform-move probability u and the four-way degree-transform choice) beyond dynnode2vec's p and q grid, the reported gains on eight of nine datasets could be produced by extra tuning freedom rather than by hub-aware sampling. The authors should separate model selection from evaluation, for example by using one or more held-out snapshots for selecting p, u, and transform type and reporting F1 only on a final test snapshot, or by reporting nested cross-validated estimates. Without such separation, the central claim is not established.
  2. [Section 5, Table 5] The conclusion that 'in all networks biased random walks tend to avoid hubs' is post hoc: the transform type (inverse or inverse-log) was chosen per dataset because it maximized the reported F1. This selection makes it unsurprising that inverse/inverse-log dominate the 'best' column, and it does not independently confirm that hub avoidance causes the improvement. A fair test would fix the transform family before seeing the evaluation data, or would compare hub-avoiding versus hub-favoring walks under identical selection protocols.
  3. [Abstract and Section 6] The abstract states that hub-aware walks 'improve downstream task performance,' but the experiments contain no downstream tasks (link prediction, node classification, or similar); the evaluation is exclusively intrinsic graph reconstruction. If downstream performance is claimed, the authors need to add such experiments; otherwise the claim should be restricted to graph reconstruction quality.
  4. [Section 4, ten-run averaging; Tables 2 and 5] No standard deviations or confidence intervals are reported even though F1 is averaged over ten runs, and several claimed improvements are small (email-eu 1.07%, fb-forum 2.56%, college-msg 3.10%, ia-primary 2.86%). Without variance information or a paired significance test across runs, these individual wins are not distinguishable from noise. The authors should report per-configuration mean and standard deviation (or a paired test) for at least the final selected configurations.
minor comments (5)
  1. [Definition 1] The phrase 'minimal set satisfying the condition' is ambiguous; specify that H is minimal by cardinality (or by the described greedy construction), and note that there is a typo ('set od nodes').
  2. [Table 1] The dataset named 'ia-primschool' in Table 1 is called 'ia-primary' in Tables 3-5; please unify the name.
  3. [Section 5, paragraph on CTDNE and STWalk] The assertion that CTDNE and STWalk 'exhibit noticeably higher graph reconstruction errors' is not supported by any table or figure; either report the numbers or omit the claim.
  4. [Algorithms 1-3] The pseudocode uses 'N C' with a space and defines max_deg over neighbors, but it does not define behavior for isolated nodes or for walks of length one; a short clarification would improve reproducibility.
  5. [Figure 2] Adding error bars or at least the 10-run standard deviation to Figure 2 would help readers judge the small differences between methods.

Circularity Check

2 steps flagged · score 6.0 of 10

DeepHub's reported F1 advantage and hub-avoidance conclusion largely reduce to per-dataset hyperparameter selection on the same metric; the finding is partly fitted rather than predicted.

  1. fitted input called prediction [Section 4 (Evaluation Methodology, baseline tuning) and Section 5 (Table 5, "Best F1-scores for DeepHub algorithm...")]
    "The baseline method, Dynnode2vec, is tuned by selecting the values of its hyperparameters p (the return back parameter) and q (the in-out parameter) that maximize the F1 score in the last snapshot. ... Table 5. Best F1-scores for DeepHub algorithm and its comparison with DN2V. ... Besides F1 scores, this table provides information about the best values of DeepHub parameters p (backtrack probability) and u (uniform sampling probability) and the type of scaling applied to degree centrality (it can be normal, log, inverse or inverse-log...)."

    DeepHub's hyperparameters (p, u, degree-transform type) are selected to maximize the same last-snapshot reconstruction F1 that is later reported as the outcome. The 8/9 win is therefore a comparison of two grid-search optima on the reported metric. Because DeepHub searches over an additional discrete axis (four transform modes) and an extra probability u, its attainable optimum is inflated by tuning freedom unrelated to hub-awareness. Reporting this optimum as "DeepHub outperforms Dynnode2vec" (Section 5) presents a fitted quantity as an independent test of the method, and no held-out snapshot or downstream task separates tuning effects from the hub-bias mechanism.

  2. fitted input called prediction [Section 5, discussion after Table 5]
    "The type of transformation applied to degree centrality is either inverse-log (6 networks) or inverse (3 networks). This means that in all networks biased random walks tend to avoid hubs."

    This finding is a restatement of the per-dataset hyperparameter selection: the transform type was chosen as the one giving the best F1 (Table 5 reports "best values" of p, u, and scaling type). Saying that all winning configurations use inverse or inverse-log transforms is equivalent to saying that the F1-optimal transform is inverse or inverse-log, not evidence that hub-avoiding walks improve embeddings. The conclusion is thus the fitted input, the selected transform, renamed as an empirical regularity about hub behavior.

full rationale

The paper's central empirical claim—that hub-aware walks improve dynamic graph embeddings—is not derived from the method's equations, but from a comparison on nine real temporal networks. The hub-bias mechanism is an a priori design choice with independent grounding in static graph experiments, so the circularity is partial rather than total. However, the evaluation protocol uses the reported metric as the selection criterion: Dynnode2vec hyperparameters are chosen to maximize last-snapshot F1, and DeepHub's p, u, and degree-transform type are likewise reported as "best values" under the same reconstruction F1. The paper then interprets the selected inverse/inverse-log transforms as evidence that "biased random walks tend to avoid hubs," which is simply the output of the hyperparameter search, not an independent confirmation of the hub-avoidance hypothesis. Because there is no held-out snapshot, no separate downstream task, and no paired significance testing, the 8/9 F1 advantage and the hub-avoidance conclusion partly reduce to selection on the evaluation metric. This fits the fitted-input-called-prediction pattern, giving a partial circularity score of 6.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central comparison depends on per-dataset fitting of p, u, and degree transform (plus the baseline p and q), and on the graph-reconstruction proxy. No code or data files are shipped.

free parameters (4)
  • p (backtrack probability) = 0, 0.15, 0.25, or 0.5 depending on network
    Grid-searched per dataset to maximize last-snapshot F1 (Table 5).
  • u (uniform move probability) = 0.15 or 0.5 depending on network
    Grid-searched per dataset to maximize last-snapshot F1 (Table 5).
  • degree transform type = inverse or inverse-log for all winning configurations
    Chosen among normal, log, inverse, and inverse-log per dataset by F1 maximization (Table 5).
  • dynnode2vec p and q (comparison baseline) = selected from {0.25, 0.5, 1, 2, 4}
    Tuned per dataset in Table 2; the comparison depends on this tuning, which uses a smaller hyperparameter space than DeepHub.
assumptions (4)
  • domain assumption Graph reconstruction F1 is a valid proxy for general-purpose dynamic graph embedding quality.
    Used as the sole evaluation metric in Sections 4 and 5; no downstream tasks are run.
  • domain assumption The minimal set of nodes whose total degree exceeds the degree of all remaining nodes is a useful hub partition.
    Definition 1 in Section 4, following reference [16].
  • domain assumption Incremental updating with random walks only from delta nodes preserves enough temporal structure for embedding quality.
    Algorithm 1 inherits the dynnode2vec update scheme from [8].
  • standard math Skip-gram word2vec training on walk sequences produces semantically meaningful node embeddings.
    Standard assumption inherited from node2vec [4] and dynnode2vec [8].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dynamic Graph Embedding Through Hub-aware Random Walks." pith.science (2026). https://pith.science/paper/G2HP4FR2

@misc{pith2026250517764,
  author       = {Pith},
  title        = {Pith review of: Dynamic Graph Embedding Through Hub-aware Random Walks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G2HP4FR2}},
  note         = {Machine review of arXiv:2505.17764}
}
read the original abstract

The role of high-degree nodes, or hubs, in shaping graph dynamics and structure is well-recognized in network science, yet their influence remains underexplored in the context of dynamic graph embedding. Recent advances in representation learning for graphs have shown that random walk-based methods can capture both structural and temporal patterns, but often overlook the impact of hubs on walk trajectories and embedding stability. In this paper, we introduce DeepHub, a method for dynamic graph embedding that explicitly integrates hub sensitivity into random walk sampling strategies. Focusing on dynnode2vec as a representative dynamic embedding method, we systematically analyze the effect of hub-biased walks across nine real-world temporal networks. Our findings reveal that standard random walks tend to overrepresent hub nodes, leading to embeddings that underfit the evolving local context of less-connected nodes. By contrast, hub-aware walks can balance exploration, resulting in embeddings that better preserve temporal neighborhood structure and improve downstream task performance. These results suggest that hub-awareness is an important yet overlooked factor in dynamic graph embedding, and our work provides a foundation for more robust, structure-sensitive representation learning in evolving networks.

Figures

Figures reproduced from arXiv: 2505.17764 by the authors.

Figure 1
Figure 1. Spearman correlations between node’s degree and graph embedding evaluation measures (F1, precision and recall) for DN2V. bedding quality of high degree nodes (hubs) and low degree nodes (non-hubs). Positive correlations mean that hubs tend to have better embedding vectors, whereas negative correlations imply the opposite [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. Comparison of F1 scores between DN2V and DeepHub. transformation applied to degree centrality is either inverse-log (6 networks) or inverse (3 networks). This means that in all networks biased random walks tend to avoid hubs. The obtained experimental findings demonstrate that DeepHub is a robust and adaptable temporal graph embedding method that consistently enhances in￾trinsic embedding quality across a wide range… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 14 canonical work pages

  1. [20]

    Statistical Analysis and Data Mining: The ASA Data Science Journal 17(2), e11676 (2024)

    Tomčić, A., Savić, M., Radovanović, M.: Hub-aware random walk graph embedding methods for classification. Statistical Analysis and Data Mining: The ASA Data Science Journal 17(2), e11676 (2024). https://doi.org/10.1002/sam.11676

    work page doi:10.1002/sam.11676 2024

  2. [1]

    ACM Computing Surveys55(1), 1–37 (2021)

    Barros, C.D., Mendonça, M.R., Vieira, A.B., Ziviani, A.: A survey on embedding dynamic graphs. ACM Computing Surveys55(1), 1–37 (2021)

    work page 2021

  3. [2]

    Dynamic Network Embeddings for Network Evolution Analysis

    Chen, C., Tao, Y., Lin, H.: Dynamic network embeddings for network evolution analysis. arXiv:1906.09860 (2019)

    work page Pith review arXiv 2019

  4. [3]

    In: 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)

    De Winter, S., Decuypere, T., Mitrović, S., Baesens, B., De Weerdt, J.: Combining temporal aspects of dynamic networks with node2vec for a more efficient dynamic link prediction. In: 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). pp. 1234–1241. IEEE (2018)

    work page 2018

  5. [4]

    In: Pro- ceedings of the 22nd ACM SIGKDD International Conference on Knowledge Dis- covery and Data Mining

    Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Pro- ceedings of the 22nd ACM SIGKDD International Conference on Knowledge Dis- covery and Data Mining. pp. 855–864 (2016)

    2016

  6. [5]

    Physics Reports 519(3), 97–125 (2012) 14 A

    Holme, P., Saramäki, J.: Temporal networks. Physics Reports 519(3), 97–125 (2012) 14 A. Tomčić et al

    work page 2012

  7. [6]

    ACM Transactions on Intelligent Systems and Technology15(1), 1–55 (2024)

    Khoshraftar, S., An, A.: A survey on graph representation learning methods. ACM Transactions on Intelligent Systems and Technology15(1), 1–55 (2024)

    2024

  8. [7]

    In: Cherifi, H., Donduran, M., Rocha, L.M., Cherifi, C., Varol, O

    Knežević, D., Savić, M., Radovanović, M.: Local intrinsic dimensionality for dy- namic graph embeddings. In: Cherifi, H., Donduran, M., Rocha, L.M., Cherifi, C., Varol, O. (eds.) Complex Networks & Their Applications XIII. pp. 374–385. Springer Nature Switzerland, Cham (2025)

    work page 2025

Show all 21 references
  1. [8]

    In: 2018 IEEE international conference on big data (Big Data)

    Mahdavi, S., Khoshraftar, S., An, A.: dynnode2vec: Scalable dynamic network embedding. In: 2018 IEEE international conference on big data (Big Data). pp. 3762–3765. IEEE (2018)

    2018

  2. [9]

    The Annals of Mathematical Statistics pp

    Mann, H.B., Whitney, D.R.: On a test of whether one of two random variables is stochastically larger than the other. The Annals of Mathematical Statistics pp. 50–60 (1947)

    1947

  3. [10]

    In: Proceedings of the International Conference on Data Science

    Mitrovic, S., De Weerdt, J.: Dyn2vec: Exploiting dynamic behaviour using dif- ference networks-based node embeddings for classification. In: Proceedings of the International Conference on Data Science. pp. 194–200. CSREA Press (2019)

    2019

  4. [11]

    In: Companion Pro- ceedings of The Web Conference 2018

    Nguyen, G.H., Lee, J.B., Rossi, R.A., Ahmed, N.K., Koh, E., Kim, S.: Continuous-time dynamic network embeddings. In: Companion Pro- ceedings of The Web Conference 2018. pp. 969–976. WWW ’18 (2018). https://doi.org/10.1145/3184558.3191526

    2018

  5. [12]

    In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence

    Nikolentzos, G., Meladianos, P., Vazirgiannis, M.: Matching node embeddings for graph similarity. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. p. 2429–2435. AAAI’17, AAAI Press (2017)

    2017

  6. [13]

    In: Proceedings of the ACM India Joint International Conference on Data Science and Management of Data

    Pandhre, S., Mittal, H., Gupta, M., Balasubramanian, V.N.: Stwalk: learning tra- jectory representations in temporal graphs. In: Proceedings of the ACM India Joint International Conference on Data Science and Management of Data. pp. 210–219. CODS-COMAD ’18, Association for Com...

    2018

  7. [14]

    In: Proceedings of the 20th ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining

    Perozzi, B., Al-Rfou, R., Skiena, S.: DeepWalk: Online learning of social rep- resentations. In: Proceedings of the 20th ACM SIGKDD International Confer- ence on Knowledge Discovery and Data Mining. KDD ’14, ACM (Aug 2014). https://doi.org/10.1145/2623330.2623732

    2014

  8. [15]

    Journal of Machine Learning Research 11(sept), 2487–2531 (2010)

    Radovanovic, M., Nanopoulos, A., Ivanovic, M.: Hubs in space: Popular near- est neighbors in high-dimensional data. Journal of Machine Learning Research 11(sept), 2487–2531 (2010)

    2010

  9. [16]

    Computing99, 1055–1079 (2017)

    Savić, M., Ivanović, M., Radovanović, M.: Analysis of high structural class coupling in object-oriented software systems. Computing99, 1055–1079 (2017)

    2017

  10. [17]

    In: Similarity Search and Applications

    Savić, M., Kurbalija, V., Radovanović, M.: Local intrinsic dimensionality and graphs: Towards LID-aware graph embedding algorithms. In: Similarity Search and Applications. pp. 159–172. Springer (2021). https://doi.org/10.1007/978-3- 030-89657-7_13

    2021 doi

  11. [18]

    Information Systems 119, 102272 (2023)

    Savić, M., Kurbalija, V., Radovanović, M.: Local intrinsic dimensionality mea- sures for graphs, with applications to graph embeddings. Information Systems 119, 102272 (2023). https://doi.org/10.1016/j.is.2023.102272

    2023

  12. [19]

    arXiv:1903.08889 (2019)

    Singer, U., Guy, I., Radinsky, K.: Node embedding over temporal graphs. arXiv:1903.08889 (2019)

    2019 arXiv

  13. [21]

    In: 2019 International Joint Conference on Neural Networks (IJCNN)

    Zhou, Y., Liu, W., Pei, Y., Wang, L., Zha, D., Fu, T.: Dynamic network embedding by semantic evolution. In: 2019 International Joint Conference on Neural Networks (IJCNN). pp. 1–8. IEEE (2019)

    2019

Pith tools

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