超图 embedding 相关论文笔记

2023-11-21 22:59:33

1 Hypergraph Neural Networks （HGNN）
2 Dynamic Hypergraph Neural Networks （DHGNN）
3 Be More with Less: Hypergraph Attention Networks for Inductive Text Classification（HyperGAT）
4 Dual-view hypergraph neural networks for attributed graph learning

超图 embedding 相关论文笔记。按照时间先后排序

名称	会议/期刊	时间
Hypergraph Neural Network	会议	2019.2
Dynamic Hypergraph Neural Networks	会议	2019
Be More with Less: Hypergraph Attention Networks for Inductive Text Classification		2020.11.1
Dual-view hypergraph neural networks for attributed graph learning		2021.1.1
Hypergraph reconstruction from network data		2021.1.15
NetVec: A Scalable Hypergraph Embedding System		2021.5.9

1 Hypergraph Neural Networks （HGNN）

这一篇论文可以说是超图 embedding 相关论文中影响力较大的一篇。文章从纯谱域角度，设计了基于超图结构数据的 embedding 模型。由于我后期的工作重点以空域方法为主，本文只对 HGNN 做简单的介绍，不详细分析。

普通图和超图的区别：

普通图：\(X\) + \(A\)
超图：\(X\) + \(H\)

文章中构造超图的方法为 KNN，构造得到的超图为 K-均匀超图。

def construct_H_with_KNN_from_distance(dis_mat, k_neig, is_probH=True, m_prob=1):
    """
    construct hypregraph incidence matrix from hypergraph node distance matrix
    :param dis_mat: node distance matrix
    :param k_neig: K nearest neighbor
    :param is_probH: prob Vertex-Edge matrix or binary
    :param m_prob: prob
    :return: N_object X N_hyperedge
    """
    n_obj = dis_mat.shape[0]
    # construct hyperedge from the central feature space of each node
    n_edge = n_obj
    H = np.zeros((n_obj, n_edge))
    for center_idx in range(n_obj):
        dis_mat[center_idx, center_idx] = 0
        dis_vec = dis_mat[center_idx]
        nearest_idx = np.array(np.argsort(dis_vec)).squeeze()
        avg_dis = np.average(dis_vec)
        if not np.any(nearest_idx[:k_neig] == center_idx):
            nearest_idx[k_neig - 1] = center_idx

        for node_idx in nearest_idx[:k_neig]:
            if is_probH:
                H[node_idx, center_idx] = np.exp(-dis_vec[0, node_idx] ** 2 / (m_prob * avg_dis) ** 2)
            else:
                H[node_idx, center_idx] = 1.0
    return H

框架图：

简单来说，就是每一个超边 \(e\) 先聚合得到每一个节点 \(v\) 的特征，然后再将超边 \(e\) 的特征反馈到其包含的每一个节点 \(v\) 上去。

实验结果（分类）：

2 Dynamic Hypergraph Neural Networks （DHGNN）

本文最大的创新点：采用图进化的思想进行超图 embedding 。本文提出了两个算法：动态超图构建（dynamic hypergraph construction，DHG）和超图卷积（HGC）。整个模型采用多个堆叠的 DHG+HGC 层，即 {DHG+HGC} - {DHG+HGC} - ... - {DHG+HGC} 。最终模型能够得到较好的 embedding 。在经过对比后，该模型是当时的 sota 方法。

图进化思想：每一次更新 embedding，都重新构造一次超图

DHG算法：

首先对当前的 embedding 矩阵 \(X\) 使用 K-Means 算法，得到簇类结果 \(C\)。 \(C[i]\) 表示第 \(i\) 簇，\(C.\text{center}\) 表示簇类中心的集合。
对每一个节点 \(u\) ，通过 KNN 算法找到和该节点最近的 k 个节点（包含自身），构成集合 \(e_b\) 。将 \(e_b\) 和 \(u\) 共同构成一个超边。
找出簇类中心离当前节点 \(u\) 的距离前 \(S-1\) 近的簇。对于每一个簇的节点集 \(C_i\)，与节点 \(u\) 共同构成一个超边。即这一步一共会构造 \(S-1\) 个超边。