Local Intrinsic Dimensionality and Graphs: Towards LID-aware Graph Embedding Algorithms
Miloš Savić, Vladimir Kurbalija and Miloš Radovanović
Local intrinsic dimensionality (LID) has many important applications in the field of machine learning (ML) and data mining (DM). Existing LID models and estimators have mostly been applied to data points in Euclidean spaces, enabling LID-aware ML/DM algorithms for tabular data. To the best of our knowledge, prior research works have not considered LID for designing or evaluating graph-based ML/DM algorithms. In this paper, we discuss potential applications of LID to graph-structured data considering graph embeddings and graph distances. Then, we propose NC-LID – a LID-related measure for quantifying the discriminatory power of the shortest-path distance with respect to natural communities of nodes as their intrinsic neighborhoods. It is shown how NC-LID can be utilized to design LID-elastic graph embedding algorithms based on random walks by proposing two LID-elastic variants of Node2Vec. Our experimental evaluation on real-world graphs demonstrates that NC-LID can point to weak parts of Node2Vec embeddings that can be improved by the proposed LID-elastic extensions.