“Are the embeddings of a graph’s degenerate core stable? What happens to the embeddings of nodes in the degenerate core as we systematically remove periphery nodes (by repeatedly peeling off κ-cores)? We discover three patterns w.r.t. instability in degenerate-core embeddings across a variety of popular graph embedding algorithms and datasets. We correlate instability with an increase in edge density, and then theoretically show that in the case of Erdös-Rényi graphs embedded with Laplacian Eigenmaps.”

Find the paper and full list of authors in the Proceedings of the 2023 SIAM International Conference on Data Mining.