# 【论文阅读】Learning with Hypergraphs: Clustering, Classification, and Embedding

### 目录

• Abstract
• Introduction
• Preliminaries
• Normalized hypergraph cut
• Random walk explanation
• Spectarl hypergraph partitioning
• Spectral hypergraph embedding
• Experiment

# Introduction

e e 为超边，图中的 e 2 e_2 表示作者写了 v 5 、 v 6 、 v 7 v_5、v_6、v_7 四篇文章， v 6 v_6 e 2 e_2 e 3 e_3 两位作者共同撰写。

# Preliminaries

：节点集合，：超边上的节点集合，：超边集合，其关系可以表示为 ( ∈ ) = _{(∈)}=

# Normalized hypergraph cut

v o l ∂ S = ∑ e ∈ ∂ S w ( e ) ∣ e ∩ S ∣ ∣ e ∩ S C ∣ δ ( e ) vol \partial S=\sum_{e\in \partial S}w(e)\frac{|e\cap S||e\cap S^C|}{\delta(e)}

a r g m i n ∅ ≠ S ⊂ V ( S ) = v o l ∂ S ( 1 / v o l S + 1 / v o l S c ) argmin_{\varnothing \ne S\subset V}(S)=vol \partial S(1/vol S+1/volS^c)

# Random walk explanation

p ( u , v ) = ∑ e ∈ E w ( e ) h ( u , e ) d ( u ) h ( v , e ) δ ( e ) p(u,v)=\sum_{e\in E}w(e)\frac{h(u,e)}{d(u)}\frac{h(v,e)}{\delta(e)}

∑ u ∈ V π ( u ) p ( u , v ) = d ( v ) v o l V = π ( v ) \sum_{u\in V}\pi(u)p(u,v)=\frac{d(v)}{vol V}=\pi(v)

v o l ∂ S v o l V = ∑ u ∈ S ∑ v ∈ S c π ( u ) p ( u , v ) \frac{vol\partial S}{vol V}=\sum_{u\in S}\sum_{v\in S^c}\pi(u)p(u,v)

c ( S ) = v o l ∂ S v o l V ( 1 v o l S / v o l V + 1 v o l S c / v o l V ) c(S)=\frac{vol\partial S}{vol V}(\frac{1}{vol S/volV}+\frac{1}{vol S^c/vol V})

# Spectarl hypergraph partitioning

a r g m i n f ∈ R ∣ V ∣ 1 2 ∑ e ∈ E ∑ { u , v } ⊆ e w ( e ) δ ( e ) ( f ( u ) d ( u ) − f ( v ) d ( v ) ) 2 argmin_{f\in R^{|V|}}\frac{1}{2}\sum_{e\in E}\sum_{\left\{u,v\right\} \subseteq e}\frac{w(e)}{\delta (e)}(\frac{f(u)}{ \sqrt{d(u)}}-\frac{f(v)}{ \sqrt{d(v)}})^2

a r g m i n f ∈ R ∣ V ∣ 1 2 ∑ e ∈ E ∑ { u , v } ⊆ e w ( e ) δ ( e ) ( f ( u ) d ( u ) − f ( v ) d ( v ) ) 2 = 2 f T Δ f argmin_{f\in R^{|V|}}\frac{1}{2}\sum_{e\in E}\sum_{\left\{u,v\right\} \subseteq e}\frac{w(e)}{\delta (e)}(\frac{f(u)}{ \sqrt{d(u)}}-\frac{f(v)}{ \sqrt{d(v)}})^2=2f^T\Delta f

A v ⃗ = λ v ⃗ A\vec{v}=\lambda \vec{v}

因此目标函数即转化为寻找拉普拉斯矩阵的最小非零特征值对应的特征向量

# Experiment

1. 构造超图，计算关联矩阵（遍历每个顶点，找到离点距离前 m m 小的点，将其权重设置为1，其余为0）得到一个 N ∗ N N*N 的矩阵， N N 为顶点个数；
2. 根据公式计算拉普拉斯矩阵；
3. 计算 l l 小特征值对应的特征向量；
4. 根据得到的特征向量进行k-means聚类。
from numpy import *
from sklearn.cluster import KMeans
import numpy as np
import  matplotlib.pyplot as plt
plt.rcParams["font.sans-serif"]=["SimHei"]
plt.rcParams['axes.unicode_minus']=False

def Eu_dis(x):#计算欧氏距离
x = np.array(x)
aa = np.sum(x**2, 1)
ab = np.dot(x,x.T)
dist_mat = aa + aa.T - 2 * ab
dist_mat[dist_mat < 0] = 0
dist_mat = np.sqrt(dist_mat)
dist_mat = np.maximum(dist_mat, dist_mat.T)
return dist_mat

def topvec(matrix,k):  #输出前k小的特征值对应的特征向量
e_vals, e_vecs = np.linalg.eig(matrix)     # 拉普拉斯矩阵热政治分解
sorted_indices=np.argsort(e_vals)
print("sorted:",sorted_indices)
print("sorted:",sorted_indices[:k])
return e_vals[sorted_indices[:k]],e_vecs[:,sorted_indices[1:k]]

def calH(new_array,k):#计算关联矩阵H
distance = Eu_dis(new_array)
distance = np.array(distance)
print(distance)

# 构建与distance维度一致的H
a, b = distance.shape
print(a, b)
H = np.zeros((a, b))  # 初始化
print(H)

# 找到每个点前k小的距离的点，在H中赋值为1（权重为1）
for i in range(a):

sorted_distance = np.argsort(distance[i])
print(sorted_distance)
for j in range(k):
H[sorted_distance[j]][i] = 1
print(H)
return H

group = np.array([[1, 101], [5, 89], [108, 5], [115, 8]])
# 数据的标签 类型
#labels = ['爱情片', '爱情片', '动作片', '动作片']
x = group.shape[0]

k=2

print(x)
new_array = group
print(new_array)

H=calH(new_array,k)  #计算H

#根据公式计算L
Dv=np.diag(np.power(np.sum(H,axis=0),-0.5))
De=np.diag(np.sum(H,axis=1))
print(Dv)
print(De)
#Dv=np.power(Dv)
H=np.mat(H)
Dv=np.mat(Dv)
W=np.mat(De)
I=np.eye(H.shape[0])
L=I-1/2*(Dv*H* W * H.T * Dv)
print(L)

#找到前k小的特征向量
val,vec=topvec(L,2)
vec_real=vec.real #返回的数值为负数，其虚部都为0，直接取实数部分

#用kMeans聚类