用随机游走首次返回时间分布构建可解释的节点嵌入
Embedding networks with the random walk first return time distribution
- 基于随机游走首次返回概率定义节点嵌入
- 在图对齐任务中优于人工设计的图度量
- 适合需要结构可解释性的网络分析场景
我们提出将随机游走的首次返回时间分布（FRTD）作为可解释且数学严谨的节点嵌入方法。FRTD为每个节点分配一个概率质量函数，可通过离散分布的标准度量定义任意两节点间的距离。我们从多个角度论证该嵌入的有效性：首先，FRTD比特征值谱更富信息量，但仍不足以完全识别图结构，表明其等价关系介于同谱性和同构性之间；其次，节点间FRTD等价反映了结构相似性；第三，实验表明该嵌入在图对齐任务中优于人工设计的图度量；最后，近似匹配目标图FRTD的随机网络也保留了其他显著特征。这些结果共同证明了FRTD是一种简洁且数学严谨的复杂网络嵌入方法。
原文摘要 · Abstract (English)
We propose the first return time distribution (FRTD) of a random walk as an interpretable and mathematically grounded node embedding. The FRTD assigns a probability mass function to each node, allowing us to define a distance between any pair of nodes using standard metrics for discrete distributions. We present several arguments to motivate the FRTD embedding. First, we show that FRTDs are strictly more informative than eigenvalue spectra, yet insufficient for complete graph identification, thus placing FRTD equivalence between cospectrality and isomorphism. Second, we argue that FRTD equivalence between nodes captures structural similarity. Third, we empirically demonstrate that the FRTD embedding outperforms manually designed graph metrics in network alignment tasks. Finally, we show that random networks that approximately match the FRTD of a desired target also preserve other salient features. Together these results demonstrate the FRTD as a simple and mathematically principled embedding for complex networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。