Skip to content

Node Importance Estimation

Name Graph Structure Multiple Predicates Node Features Signal (Signal) Signal (Multi) 备注
PR ✅ ❌ ❌ ❌ ❌
PPR ✅ ❌ ❌ ✅ ❌
HAR ✅ ✅ ✅ ❌
GENII ✅ ✅ ✅ ✅ ❌
MultiIImport ✅ ✅ ✅ ✅ ✅
HITS ✅ ❌ ❌ ❌ ❌
IPM2016 ✅ ❌ ❌ ❌ ❌ 自定义的多signal

Random Walk

PageRank (PR)

\[ \mathbf{r}^\top=\mathbf{r}^\top((1-\alpha)\mathbf{W} + \alpha \mathbf{1} \mathbf{u}^\top) \]
\[ \mathbf{u}=\frac{1}{N}\mathbf{1} \]

Personalized PageRank (PPR)

\[ \mathbf{r}^\top=\mathbf{r}^\top((1-\alpha)\mathbf{W} + \alpha \mathbf{1} \mathbf{u}^\top) \]

每一步都可能按照指定的概率到达每一个节点

Random Walk with Restart (RWR)

\[ \mathbf{r}^\top=(1-\alpha)\mathbf{r}^\top\mathbf{W} + \alpha \mathbf{u}^\top \]

每一步都有一定概率直接回到出发的节点，出发的概率是\(\mathbf{u}\)指定的。在这种情况下，显然RWR和PPR是等价的：

\[ \mathbf{r}^\top((1-\alpha)\mathbf{W} + \alpha \mathbf{1} \mathbf{u}^\top)=(1-\alpha)\mathbf{r}^\top\mathbf{W}+\alpha\mathbf{r}^\top\mathbf{1}\mathbf{u}^\top=(1-\alpha)\mathbf{r}^\top\mathbf{W}+\alpha\mathbf{u}^\top \]

被用来计算两个节点的相关性，比如计算节点\(j\)相对于\(i\)的相关性，那么

\[ \mathbf{r}^{(i)\top}=(1-\alpha)\mathbf{r}^{(i)\top}\mathbf{W} + \alpha \mathbf{e}^{(i)^\top} \]

\(\mathbf{r}^{(i)}_j\)就是要的相关性

一般，\(\mathbf{r}^{(i)}_j\neq \mathbf{r}^{(j)}_i\)，因为\(\mathbf{r}^{(i)}_j=\mathbf{e}^{(j)\top}\alpha(\mathbf{I}- (1-\alpha)\mathbf{W})^\top\mathbf{e}^{(i)}\)

HAR

GENI

MultiImport

MultiImport Inferring Node Importance in a Knowled

IPM2016

Last update : July 1, 2023
Created : February 13, 2023

Comments

Comments