Feature homophily metric

• 概
• 符号说明
• Homophily on Feature Aspect

[1] Chen Y., Luo Y., Tang J., Yang L., Qiu S., Wang C. and Cao X. LSGNN: Towards general graph neural network in node classification by local similarity. 2023.

[2] Jin D., Wang R., Ge M., He D., Li X., Lin W. and Zhang W. RAW-GNN: Random walk aggregation based graph neural network. 2022.

[3] Lee S. Y., Kim S., Bu F., Yoo J., Tang J. and Shin K. Feature distribution on graph topology mediates the effect of graph convolution: Homophily perspective. ICML, 2023.

[4] Yang L., Li M., Liu L., Niu B., Wang C., Cao X. and Guo Y. Diverse message passing for attribute with heterophily. NeurIPS, 2021.

Zheng Y., Luan S. and Chen L. What is missing in homophily? Disentangling graph homophily for graph neural networks. 2024.

概

收集了一些基于 feature 而不是 label 的 homophily 的指标.

符号说明

• \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\), 图;
• \(\bm{X} \in \mathbb{R}^{|\mathcal{V}| \times M}\), node features;
• \(\mathcal{N}_u,\), 节点 \(u\) 的一阶邻居;

Homophily on Feature Aspect

• Generalized edge homophily [2]:

  \[h_{GE}(\mathcal{G}, \bm{X}) = \frac{1}{|\mathcal{E}|} \sum_{e_{uv} \in \mathcal{E}} \text{sim}(\bm{x}_u, \bm{x}_v), \]

  其中 \(\text{sim}(\cdot, \cdot)\) 可以是 cosine 相似度, 欧式距离等.

• Local Similarity [1]:

  \[h_{LS-cos} (\mathcal{G}, \bm{X}) = \frac{1}{|\mathcal{V}|} \sum_{u \in \mathcal{V}} \frac{1}{d_u} \sum_{v \in \mathcal{N}_u} \text{sim}(\bm{x}_u, \bm{x}_v). \]

• Attribute homophily:

  \[h_{attr, m}(\mathcal{G}, \bm{X}_{:, m}) = \frac{1}{\sum_{u \in \mathcal{V}} X_{u, m}} \sum_{u \in \mathcal{V}} \bigg( X_{u, m} \frac{ \sum_{v \in \mathcal{N}_u} X_{v, m} }{ d_u } \bigg), \\ h_{attr}(\mathcal{G}, \bm{X}) = \sum_{m=1}^M h_{attr, m} (\mathcal{G}, \bm{X}_{:, m}). \]

• Class-controlled feature homophily [3]:

  \[h_{CF}(\mathcal{G}, \bm{X}, \bm{Y}) = \frac{1}{|\mathcal{V}|} \sum_{v \in \mathcal{V}} \frac{1}{d_u} \sum_{v \in \mathcal{N}_u} \big( d(v, \mathcal{V} \setminus \{u\}), d(v, \{u\}) \big), \\ d(u, \mathcal{V}') = \frac{1}{|\mathcal{V}'|} \sum_{v \in \mathcal{V}'} \| (\bm{x}_u| \bm{Y}) - (\bm{x}_v | \bm{Y}) \|, \\ \bm{x}_u | \bm{Y} = \bm{x}_u - \bigg( \frac{ \sum_{Y_u = Y_v} \bm{x}_v }{ |\{ v| Y_u = Y_v, v \in \mathcal{V} \}| } \bigg). \]