# Enhancing Distance-Based Graph Autoencoders with Structural Penalties for Dynamic Graph Embedding

arXiv: https://arxiv.org/abs/2608.18762 · HTML: https://mlsanity.com/paper/2608.18762/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 19 references that are in the map.
- First posted on arXiv 19 Aug 2026.

## Builds on (most cited first, 14 of 14)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [A Survey on Embedding Dynamic Graphs](https://mlsanity.com/paper/2101.01229/) (2021)
- [dynnode2vec: Scalable Dynamic Network Embedding](https://mlsanity.com/paper/1812.02356/) (2018)
- [STWalk: Learning Trajectory Representations in Temporal Graphs](https://mlsanity.com/paper/1711.04150/) (2017)
- [Local Intrinsic Dimensionality Measures for Graphs, with Applications to Graph Embeddings](https://mlsanity.com/paper/2208.11986/) (2022)
- [Hub-aware Random Walk Graph Embedding Methods for Classification](https://mlsanity.com/paper/2209.07603/) (2022)
- [Local Intrinsic Dimensionality for Dynamic Graph Embeddings](https://mlsanity.com/paper/2411.16145/) (2024)
- [Dynamic Graph Embedding Through Hub-aware Random Walks](https://mlsanity.com/paper/2505.17764/) (2025)

## Abstract (arXiv)

Graph autoencoders (GAEs) are widely used for learning representations of dynamic graphs. However, their optimisation objectives typically do not take structural heterogeneity across nodes into account. We propose three distance-based GAE variants that incorporate structural penalties into the reconstruction loss. All variants share a two-layer Graph Convolutional Network encoder and a Euclidean-distance decoder trained with distance-based reconstruction objectives. We extend sparsity-corrected loss with two node-level regularization terms: (i) a hub penalty based on degree centrality, and (ii) a penalty based on Natural Community Local Intrinsic Dimensionality (NC-LID). The paper is motivated by prior evidence linking high NC-LID to reduced embedding quality. The proposed methods are designed to emphasize reconstruction errors for structurally ambiguous nodes. Experiments on multiple dynamic graph data sets show that incorporating NC-LID-based regularization consistently improves reconstruction performance over the baseline without structural regularization and the method using hub-aware regularization. These findings highlight NC-LID as a useful structural signal for enhancing distance-based graph autoencoders in dynamic settings.