Local Intrinsic Dimensionality for Dynamic Graph Embeddings

Du\v{s}ica Kne\v{z}evi\'c; Milo\v{s} Radovanovi\'c; Milo\v{s} Savi\'c

REVIEW 3 major objections 4 minor 14 references

Local Intrinsic Dimensionality for Dynamic Graph Embeddings

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper claims that NC-LID, a local intrinsic dimensionality measure for static graphs, can identify nodes whose dynamic graph embedding vectors fail to preserve temporal structure.

desk verdict Plausible empirical finding that per-snapshot NC-LID correlates negatively with dynnode2vec embedding quality, but the pooled node-snapshot statistics overstate significance. read the letter →

arxiv 2411.16145 v1 pith:YLDUXDOF submitted 2024-11-25 cs.LG

Dušica Knežević , Miloš Savić , Miloš Radovanović This is my paper · ORCID

classification cs.LG

keywords dynamicgraphsgraphembeddingslocalintrinsicdimensionalityNC-LIDdynnode2vecrandomwalkslinkreconstructiontemporalnetworks

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

The paper asks whether NC-LID, a measure of local intrinsic dimensionality originally defined for static graphs, can identify nodes whose dynamic graph embeddings are poorly constructed. Using dynnode2vec on 10 real-world dynamic networks, the authors find significant negative Spearman correlations between NC-LID and the F1 score of link reconstruction in 6 networks, with coefficients from -0.19 to -0.41. Mann-Whitney tests show that in 6 of the 8 networks with significant differences, high-NC-LID nodes have significantly lower F1 than low-NC-LID nodes. The authors conclude that NC-LID is a good indicator of nodes whose embedding vectors fail to preserve temporal graph structure, and that this is a first step toward LID-aware dynamic graph embedding algorithms.

What carries the argument

The central object is NC-LID(n) = $-\ln\left(\frac{|S|}{D(n,k)}\right)$, where $S$ is the natural community of node $n$ found by a fitness-based algorithm, $k$ is the largest shortest-path distance from $n$ to any node in $S$, and $D(n,k)$ counts nodes within $k$ hops. It measures how irregularly shaped the node's intrinsic locality is: low values mean shortest-path distance cleanly separates the community from the rest of the graph, high values mean the community blends into surrounding structure. The paper's methodology relies on this scalar as a per-node, per-snapshot signal and correlates it with reconstruction-based quality metrics (precision, recall, F1) of dynnode2vec embeddings, then compares F1 of high- versus low-NC-LID groups with Mann-Whitney U tests.

What would settle it

Run the same pipeline on a synthetic dynamic graph with known community evolution and controlled random-walk embeddings; compute per-node NC-LID and F1 for link reconstruction. If the Spearman correlation between NC-LID and F1 is non-negative, or if high-NC-LID nodes do not have lower F1, the claimed indicator property fails.

Watch

Extended reading notes

Core claim

The central claim is that NC-LID, computed independently on each snapshot of a dynamic graph, serves as a proxy for where dynnode2vec's embeddings lose local structure. Nodes with high NC-LID have natural communities that are hard to separate from the rest of the graph by shortest-path distance; the paper shows these nodes tend to have lower precision, recall, and F1 in graph reconstruction from embeddings. This relationship is not universal: two networks show no significant F1 difference, and one network's embeddings are so poor that its correlations are uninformative. The authors read the overall pattern as evidence that dynamic embedding methods can be improved by steering random-walk sampling toward high-NC-LID nodes.

Load-bearing premise

The analysis assumes that NC-LID computed separately on each static snapshot captures the structure relevant to how well dynnode2vec preserves temporal structure, and that treating every node-snapshot observation as independent gives valid significance levels.

Editorial extensions

If this is right

If NC-LID reliably marks weak nodes, dynnode2vec and similar random-walk methods can allocate more random walks to high-NC-LID nodes without increasing the total walk budget.
Random-walk bias parameters $p$ and $q$ could be personalized by NC-LID to keep walks inside complex natural communities longer, potentially improving the embeddings of those nodes.
The same methodology transfers to any dynamic embedding method built on discrete snapshots, since per-snapshot NC-LID needs no modification.
In continuous-time representations, replacing shortest-path distance with temporal distance would extend the indicator to event-based dynamic graphs.
Link-reconstruction F1 can serve as a cheap, task-agnostic node-level quality monitor for dynamic embeddings.

Reading between the lines

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

An editorial inference is that the mechanism behind the correlation may be static community complexity rather than temporality: the same negative relationship might appear for static node2vec embeddings on each snapshot, which would mean the dynamic setting adds little beyond what static NC-LID already predicts.
A testable extension is to compare pooled per-snapshot NC-LID with NC-LID computed on the time-aggregated graph; if the aggregated version loses the correlation, event ordering is the informative part.
Because node-snapshot observations are pooled, the reported p-values treat repeated appearances of the same node as independent; a node-level bootstrap or mixed-effects model would give a stricter significance check.

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.

Desk Editor's Note

read the letter

Fairly straightforward paper: it takes NC-LID, a static-graph local intrinsic dimensionality measure, computes it per snapshot for ten dynamic networks, and correlates it with the quality of dynnode2vec embeddings measured by graph reconstruction F1. The new content is the correlation study itself; the adaptation is exactly what you'd expect. That's fine as a first step, and the paper is honest about it.

What the paper does well: the experimental design is clear, the datasets are public and standard, and the authors report per-network details. The main observation—that in six of ten networks, nodes with higher NC-LID tend to have lower F1—is plausible and worth checking. They also run Mann-Whitney tests comparing high- vs low-NC-LID nodes, and the directions line up with the correlations.

The soft spot is statistical. The correlations and MWU tests pool all node-snapshot observations, so the same node contributes many times, with embeddings and NC-LID values that are highly correlated across snapshots. That inflates the effective sample size and makes the p-values look far stronger than they are. The MWU assumption of independent observations is violated. Recomputing with one observation per node (e.g., last snapshot or a node-level aggregate) is the obvious check. The paper also doesn't correct for multiple testing across ten networks, and the exclusion of ia-realitycall is post hoc—though the stated reason, that the embedding itself is essentially random, is defensible. A second issue is that per-snapshot NC-LID ignores temporal paths and event ordering, so the phrase 'temporal graph structure' is doing more work than the measure does.

If the per-node analysis still shows a negative association in most networks, the paper is a useful empirical result for the dynamic-graph-embedding community. As it stands, the central claim is plausible but the evidence is weaker than reported. No code or data is released, which makes the numbers harder to check.

I'd send it to review, but with a clear request for a proper independence-aware analysis. The paper is a legitimate contribution to a narrow subfield, and the authors are not overclaiming—they call it a first step, which it is.

Referee Report

3 major / 4 minor

Summary. The paper proposes an adaptation of the static graph measure NC-LID (local intrinsic dimensionality based on natural communities) to dynamic graphs, and an evaluation methodology for testing whether NC-LID identifies nodes whose dynamic graph embeddings poorly preserve local structure. The authors apply dynnode2vec to ten real-world dynamic networks, computing per-snapshot NC-LID values and comparing them with node-level F1 scores from graph reconstruction. They report significant negative Spearman correlations between NC-LID and F1 for six networks, and Mann-Whitney U tests showing significantly lower F1 for high-NC-LID nodes in six of eight networks with significant differences. The paper concludes that NC-LID is a promising indicator for guiding LID-aware dynamic embedding methods.

Significance. If the reported relationship holds, the result is a useful first step toward adaptive, LID-aware dynamic graph embedding, with a concrete evaluation methodology and a clearly stated future extension to modify random-walk sampling based on NC-LID. The use of graph reconstruction F1 as an external criterion is a strength: the evaluation metric is computed independently of NC-LID, so the main correlation claim is not circular. The paper is also transparent about its data sources and hyperparameter choices. However, the statistical support needs methodological strengthening before the central claim can be accepted.

major comments (3)

[Section 3, Spearman correlations and MWU tests] The correlations and Mann-Whitney U tests are computed over pooled node-snapshot observations, i.e., each node contributes one observation in every snapshot in which it appears. This violates the independence assumption of both Spearman's rank correlation and the MWU test. Nodes recur across snapshots with highly persistent embedding vectors and NC-LID values, so the effective sample size is much smaller than the pooled count and the reported p-values (e.g., in Table 3) are unreliable. Please reanalyze with one observation per node (for example, using the last snapshot, or per-node averaged NC-LID and F1 across snapshots), or use a mixed-effects model or block bootstrap that accounts for node-level clustering, and report whether the significant negative correlations and MWU differences survive.
[Section 4, exclusion of ia-realitycall] The paper sets aside ia-realitycall from the interpretation of Figure 3 because its dynnode2vec embeddings have extremely low F1 (0.0362 in Table 2), stating that "the correlation results obtained for this network can not be used to derive a meaningful conclusion." This exclusion is introduced after observing that ia-realitycall exhibits a positive correlation, opposite to the claimed direction. Without a pre-specified, uniformly applied quality threshold, this post-hoc removal weakens the robustness of the central claim. Please either include ia-realitycall in the summary statistics or justify the exclusion with an objective criterion (e.g., a minimum F1 threshold) applied to all networks before looking at the correlations.
[Section 2 and Section 4] The NC-LID variant used in the experiments is the static, per-snapshot definition: it is computed independently on each snapshot using shortest-path distances and natural communities. This measure does not incorporate temporal paths, event ordering, or temporal neighborhoods. The abstract and conclusions state that NC-LID indicates nodes whose embeddings "do not tend to preserve temporal graph structure well," but the experiments actually test preservation of static connectedness within snapshot graphs. Please either align the language with what is measured, or additionally evaluate the continuous-time adaptation based on temporal distances described in Section 2, and clarify which notion of "temporal structure" the reported correlations support.

minor comments (4)

[Throughout] There are several typos: "exibited" should be "exhibited", "Spreman" should be "Spearman", "Dijsktra" should be "Dijkstra", and "shorest-path" should be "shortest-path".
[Figure 3] Figure 3 shows the Spearman correlations but no numerical values or p-values. Adding per-network sample sizes, exact correlation coefficients, and significance markers would make the results easier to assess, especially given the pooling issue raised above.
[Table 3] The probabilities of superiority PS(H) and PS(L) do not sum to 1 for several rows (e.g., ia-realitycall: 0.1701 + 0.0817 = 0.2518). This presumably reflects ties in F1 scores; please state explicitly how ties are treated in the computation of these probabilities.
[Section 3] The hyperparameter tuning description says p and q are chosen from {0.25, 0.50, 1, 2, 4} and the number of walks per node and walk length are fixed, but it does not report the final selected hyperparameters for each network beyond those in Table 2. Listing the tuned p/q values for all networks would improve reproducibility.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: NC-LID is evaluated against independently computed dynnode2vec reconstruction F1; self-citations supply definitions and motivation, not the target result.

full rationale

The central claim is empirical: NC-LID values computed from graph snapshots correlate negatively with dynnode2vec embedding quality measured by graph-reconstruction F1. This is not circular because the two quantities are computed independently. NC-LID is derived from natural communities and shortest-path distances in the original graph, while F1, precision, and recall are obtained by reconstructing the graph from dynnode2vec embeddings and comparing against the original edges; NC-LID is not used in the embedding generation or in the reconstruction-evaluation pipeline. No equation in the paper defines NC-LID in terms of F1, nor F1 in terms of NC-LID. The adaptation to dynamic graphs is a direct application of the static NC-LID definition snapshot-by-snapshot, or a substitution of temporal distance for shortest-path distance, so no self-definitional reduction is present. The self-citations to the authors' prior work [12,13,6] provide the NC-LID definition and the motivating result that LID-aware extensions improved static node2vec-based embeddings; these citations are background and motivation, not the evidence for the dynamic correlation reported here. The evaluation is self-contained against external benchmarks: dynnode2vec embeddings, reconstruction F1, MWU tests, and centrality measures are all external to the NC-LID construction. There are legitimate statistical concerns, such as pooling repeated node-snapshot observations in the MWU tests and the post-hoc exclusion of ia-realitycall, but these are validity threats rather than circularity: they do not make the claimed correlation true by construction. Thus the paper has at most minor, non-load-bearing self-citation and no circular derivation chain.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new theoretical entities. Its central empirical claim rests on the NC-LID measure from the authors' prior work, the graph reconstruction quality metric, and the dynnode2vec hyperparameter selection, all of which are external inputs. The main unstated assumption is the independence of pooled node-snapshot observations.

free parameters (1)

dynnode2vec hyperparameters (p, q, embedding dimension) = Varies per network; see Table 2 (e.g., fb-forum: p=1, q=1, dim=200)
The correlations are computed on embeddings generated with these grid-searched values, so the central claim depends on this model selection.

assumptions (3)

domain assumption Pooling node-snapshot pairs for correlation and MWU tests assumes independence of repeated observations of the same node.
Used in Section 4 for all correlations and tests; repeated nodes over snapshots create dependence that is not modeled.
domain assumption Graph reconstruction via connecting the |E| closest embedding pairs is a valid measure of intrinsic embedding quality.
Adopted from the authors' prior work [13]; the paper does not validate this metric for dynamic graphs.
domain assumption dynnode2vec is representative of random-walk based dynamic graph embedding methods.
The paper uses only dynnode2vec and generalizes conclusions to dynamic graph embeddings broadly.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Local Intrinsic Dimensionality for Dynamic Graph Embeddings." pith.science (2026). https://pith.science/paper/YLDUXDOF

@misc{pith2026241116145,
  author       = {Pith},
  title        = {Pith review of: Local Intrinsic Dimensionality for Dynamic Graph Embeddings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YLDUXDOF}},
  note         = {Machine review of arXiv:2411.16145}
}

read the original abstract

The notion of local intrinsic dimensionality (LID) has important theoretical implications and practical applications in the fields of data mining and machine learning. Recent research efforts indicate that LID measures defined for graphs can improve graph representational learning methods based on random walks. In this paper, we discuss how NC-LID, a LID measure designed for static graphs, can be adapted for dynamic networks. Focusing on dynnode2vec as the most representative dynamic graph embedding method based on random walks, we examine correlations between NC-LID and the intrinsic quality of 10 real-world dynamic network embeddings. The obtained results show that NC-LID can be used as a good indicator of nodes whose embedding vectors do not tend to preserve temporal graph structure well. Thus, our empirical findings constitute the first step towards LID-aware dynamic graph embedding methods.

Figures

Figures reproduced from arXiv: 2411.16145 by the authors.

**Figure 1.** Average and maximal NC-LID per network. correlations), while in some networks such nodes tend to occupy central positions and be the most important nodes for dynamic processes running on networks. The results of dynnode2vec tuning are presented in [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

**Figure 2.** Spearman correlations between NC-LID and node centrality measures [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Spearman correlations between NC-LID and graph embedding evaluation measures (F1, precision and recall). The networks are sorted from the lowest to the highest correlation between NC-LID and F1. For the first 6 networks shown in [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 6 canonical work pages

[1]

ACM Computing Surveys (CSUR) 55(1) (2021)

Barros, C.D.T., Mendon¸ ca, M.R.F., Vieira, A.B., Ziviani, A.: A survey on em- bedding dynamic graphs. ACM Computing Surveys (CSUR) 55(1) (2021). DOI 10.1145/3483595

doi:10.1145/3483595 2021
[2]

In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, p

Grover, A., Leskovec, J.: Node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, p. 855–864. Association for Computing Machinery, New York, NY, USA (2016). DOI 10.1145/2939672.2939754

arXiv 2016
[3]

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

Holme, P., Saram¨ aki, J.: Temporal networks. Physics Reports 519(3), 97–125 (2012). DOI 10.1016/j.physrep.2012.03.001. Temporal Networks

doi:10.1016/j.physrep.2012.03.001 2012
[4]

In: 2013 IEEE 13th International Conference on Data Mining Workshops, pp

Houle, M.E.: Dimensionality, discriminability, density and distance distributions. In: 2013 IEEE 13th International Conference on Data Mining Workshops, pp. 468– 473 (2013). DOI 10.1109/ICDMW.2013.139

work page doi:10.1109/icdmw.2013.139 2013
[5]

ACM Transactions on Intelligent Systems and Technology 15(1) (2024)

Khoshraftar, S., An, A.: A survey on graph representation learning methods. ACM Transactions on Intelligent Systems and Technology 15(1) (2024). DOI 10.1145/ 3633518

work page 2024
[6]

Kneˇ zevi´ c, D., Babi´ c, J., Savi´ c, M., Radovanovi´ c, M.: Evaluation of LID-Aware Graph Embedding Methods for Node Clustering. In: T. Skopal, F. Falchi, J. Lokoˇ c, M.L. Sapino, I. Bartolini, M. Patella (eds.) Similarity Search and Ap- plications, pp. 222–233. Springer International Publishing, Cham (2022). DOI 10.1007/978-3-031-17849-8 18

work page doi:10.1007/978-3-031-17849-8 2022
[7]

New Journal of Physics 11(3), 033,015 (2009)

Lancichinetti, A., Fortunato, S., Kert´ esz, J.: Detecting the overlapping and hierar- chical community structure in complex networks. New Journal of Physics 11(3), 033,015 (2009). DOI 10.1088/1367-2630/11/3/033015

work page doi:10.1088/1367-2630/11/3/033015 2009
[8]

In: 2018 IEEE International Conference on Big Data (Big Data), pp

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 Computer Society, Los Alamitos, CA, USA (2018). DOI 10.1109/BigData.2018.8621910

arXiv 2018

Show all 14 references

[9]

The Annals of Mathematical Statistics 18(1), 50 – 60 (1947)

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 18(1), 50 – 60 (1947). DOI 10.1214/aoms/1177730491

1947
[10]

Pan, R.K., Saram¨ aki, J.: Path lengths, correlations, and centrality in temporal networks. Phys. Rev. E 84, 016,105 (2011). DOI 10.1103/PhysRevE.84.016105 12 Duˇ sica Kneˇ zevi´ c et al

2011 doi
[11]

Savi´ c, M., Ivanovi´ c, M., Jain, L.C.: Fundamentals of Complex Network Analy- sis, pp. 17–56. Springer International Publishing, Cham (2019). DOI 10.1007/ 978-3-319-91196-0 2

2019
[12]

Savi´ c, M., Kurbalija, V., Radovanovi´ c, M.: Local intrinsic dimensionality and graphs: Towards LID-aware graph embedding algorithms. In: N. Reyes, R. Connor, N. Kriege, D. Kazempour, I. Bartolini, E. Schubert, J.J. Chen (eds.) Similarity Search and Applications, pp. 159–172...

2021 doi
[13]

Information Systems 119, 102,272 (2023)

Savi´ c, M., Kurbalija, V., Radovanovi´ c, M.: Local intrinsic dimensionality measures for graphs, with applications to graph embeddings. Information Systems 119, 102,272 (2023). DOI https://doi.org/10.1016/j.is.2023.102272

2023
[14]

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

Tomˇ ci´ c, A., Savi´ c, M., Radovanovi´ c, M.: Hub-aware random walk graph embedding methods for classification. Statistical Analysis and Data Mining: The ASA Data Science Journal 17(2), e11,676 (2024). DOI 10.1002/sam.11676

2024 doi

Pith tools

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

[1] [1]

ACM Computing Surveys (CSUR) 55(1) (2021)

Barros, C.D.T., Mendon¸ ca, M.R.F., Vieira, A.B., Ziviani, A.: A survey on em- bedding dynamic graphs. ACM Computing Surveys (CSUR) 55(1) (2021). DOI 10.1145/3483595

doi:10.1145/3483595 2021

[2] [2]

In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, p

Grover, A., Leskovec, J.: Node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, p. 855–864. Association for Computing Machinery, New York, NY, USA (2016). DOI 10.1145/2939672.2939754

arXiv 2016

[3] [3]

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

Holme, P., Saram¨ aki, J.: Temporal networks. Physics Reports 519(3), 97–125 (2012). DOI 10.1016/j.physrep.2012.03.001. Temporal Networks

doi:10.1016/j.physrep.2012.03.001 2012

[4] [4]

In: 2013 IEEE 13th International Conference on Data Mining Workshops, pp

Houle, M.E.: Dimensionality, discriminability, density and distance distributions. In: 2013 IEEE 13th International Conference on Data Mining Workshops, pp. 468– 473 (2013). DOI 10.1109/ICDMW.2013.139

work page doi:10.1109/icdmw.2013.139 2013

[5] [5]

ACM Transactions on Intelligent Systems and Technology 15(1) (2024)

Khoshraftar, S., An, A.: A survey on graph representation learning methods. ACM Transactions on Intelligent Systems and Technology 15(1) (2024). DOI 10.1145/ 3633518

work page 2024

[6] [6]

Kneˇ zevi´ c, D., Babi´ c, J., Savi´ c, M., Radovanovi´ c, M.: Evaluation of LID-Aware Graph Embedding Methods for Node Clustering. In: T. Skopal, F. Falchi, J. Lokoˇ c, M.L. Sapino, I. Bartolini, M. Patella (eds.) Similarity Search and Ap- plications, pp. 222–233. Springer International Publishing, Cham (2022). DOI 10.1007/978-3-031-17849-8 18

work page doi:10.1007/978-3-031-17849-8 2022

[7] [7]

New Journal of Physics 11(3), 033,015 (2009)

Lancichinetti, A., Fortunato, S., Kert´ esz, J.: Detecting the overlapping and hierar- chical community structure in complex networks. New Journal of Physics 11(3), 033,015 (2009). DOI 10.1088/1367-2630/11/3/033015

work page doi:10.1088/1367-2630/11/3/033015 2009

[8] [8]

In: 2018 IEEE International Conference on Big Data (Big Data), pp

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 Computer Society, Los Alamitos, CA, USA (2018). DOI 10.1109/BigData.2018.8621910

arXiv 2018