STABLE: Identifying and Mitigating Instability in Embeddings of the Degenerate Core
STABLE: Identifying and Mitigating Instability in Embeddings of the Degenerate Core
复制标题
DOI：
10.1137/1.9781611977653.ch46
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
David Liu;Tina Eliassi-Rad
中科院分区：
文献类型：
--
作者：
David Liu;Tina Eliassi-Rad
图的简并核的嵌入是稳定的吗？当我们系统地移除外围节点（通过反复剥离k核）时，退化核中的节点嵌入会发生什么？我们在各种流行的图嵌入算法和数据集上发现了退化核嵌入中的三种不稳定性模式。我们将不稳定性与边缘密度的增加联系起来，然后从理论上表明，在嵌入了拉普拉斯特征映射的Erd¨os-R’enyi图的情况下，随着密度的增加，最佳和最差的嵌入可能变得越来越难以区分。此外，我们还提出了STABLE算法，该算法采用现有的图嵌入算法，使其具有稳定性。我们展示了STABLE在使简并核嵌入稳定和仍然产生最先进的链路预测性能方面的有效性。
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 k -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¨os-R´enyi graphs embedded with Laplacian Eigenmaps, the best and worst possible embeddings become less distinguishable as density increases. Furthermore, we present the STABLE algo-rithm, which takes an existing graph embedding algorithm and makes it stable. We show the effectiveness of STABLE in terms of making the degenerate-core embedding stable and still producing state-of-the-art link prediction performance.