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

Aleksandar Tomčić; Miloš Savić; Miloš Radovanović

cs.LGAug 19, 2026

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

Authors: Aleksandar Tomčić, Miloš Savić, Miloš Radovanović

Organizations: Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Serbia Trg Dositeja Obradovi´ca 4, 21000 Novi Sad, Serbia

Abstract

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.

Figures & tables

Dataset	Res.	Snaps.	Max nodes	Max edges
radoslaw-email	month	9	151	1,675
ia-hospital-ward-proximity-attr	day	5	54	492
ia-contacts_hypertext2009	day	3	102	1,062
ia-enron-employees	3-months	13	140	823
ia-primary-school-proximity-attr	day	2	241	5,923
fb-forum	month	6	815	5,838

Table 1: Experimental datasets. Max nodes and max edges refer to the largest individual snapshot.

Table 2

$d$	Basic	Hub	LID
fb-forum
10	0.3754	0.3562	0.4098
25	0.5797	0.5708	0.5925
50	0.6374	0.6277	0.6431
100	0.6522	0.6439	0.6622
200	0.6638	0.6600	$\mathbf{0.6681}^{\star}$

Table 4: Mean reconstruction

F_{1}

for fb-forum , email-Eu-core-temporal , CollegeMsg , and fb-messages .

Dataset	$F_{1}$	$d^{\star}$	$F_{1}$	$d^{\star}$	$F_{1}$	$d^{\star}$
	Basic		Hub		LID
radoslaw-email	0.6099	100	0.6000	100	0.6229	100
hospital-ward	0.8207	200	0.7968	100	0.8222	200
hypertext2009	0.7290	100	0.7197	100	0.7214	100
enron-employees	0.8098	100	0.7999	100	0.8140	100
primary-school	0.7718	200	0.7706	200	0.7706	100

Table 5: Best mean reconstruction

F_{1}

per dataset and model.

d^{\star}

is the optimal dimension. Bold marks the winner per dataset. Win count tallies best

F_{1}

victories across all 9 datasets.

Explore similar work

GeoGAE: Scalable Graph-Level Autoencoding via Hyperball Cloud Representations
Sep 28, 2026Radosław Nowak, Anna Bielawska, Bogusz Stefańczyk +2Graph Representation Learning Graph Representations
Institute of Theoretical and Applied Informatics Polish Academy of Sciences · IDEAS Research Institute · Faculty of Mathematics, Informatics and Mechanics Warsaw University of Technology
Scalable and Efficient Joint Spiking Embedding Predictive Architecture for Large-Scale Dynamic Graphs
Jul 20, 2026Huizhe Zhang, Yuchang Zhu, Huazhen Zhong +2Spiking Neural Networks Autoencoder Architectures
Sun Yat-sen University Guangzhou, China · Sun Yat-sen University Zhuhai, China
MABLE: Masked Autoencoding with Bi-Lipschitz Decoding for Embeddings and Graph Metric Learning
Jul 3, 2026Yaniv Shulman, Shaghayegh Akbarpour, Jack B. MuirGraph Representation Learning Behavioral Embeddings
Fleet Space Technologies, Adelaide, Australia · Research School of Earth Sciences, Australian National University, Acton, Australia

Sep 28, 2026, cs.LGJ/K move · Enter open · S save

GeoGAE: Scalable Graph-Level Autoencoding via Hyperball Cloud Representations

Radosław Nowak, Anna Bielawska, Bogusz Stefańczyk, Maciej Sanocki+1

Institute of Theoretical and Applied Informatics Polish Academy of Sciences · IDEAS Research Institute · Faculty of Mathematics, Informatics and Mechanics Warsaw University of Technology

Graph Representation Learning Graph Representations Autoencoder Architectures Geogs-Slam Sphere

Open paper AskPDF arXiv

Embedding structured objects into Euclidean spaces has enabled a wide range of successful machine learning applications. Such objects include words, documents, image patches, time series, and graph nodes. In contrast, embedding entire graphs remains a challenging problem. Existing methods either sustain the original order of the graph nodes or match the output nodes to the input ones, both of which create scalability issues. In this work, we propose a graph representation as a cloud of hyperballs, which allows us to define a specific, typically unique, node ordering. Based on this representation, we propose GeoGAE, an autoencoder, in which the Transformer encoder translates a hyperball cloud into a graph-level embedding, and the Transformer decoder translates the graph-level embedding back into the graph. This formulation enables the model to capture both the global graph structure and local relational patterns. We evaluate our method on multiple graph datasets, spanning various domains. The results demonstrate effectiveness of our method in encoding and reconstructing graphs from their embeddings.

Abstract

Explore similar work

GeoGAE: Scalable Graph-Level Autoencoding via Hyperball Cloud Representations

Scalable and Efficient Joint Spiking Embedding Predictive Architecture for Large-Scale Dynamic Graphs

MABLE: Masked Autoencoding with Bi-Lipschitz Decoding for Embeddings and Graph Metric Learning