![论文阅读笔记：[ICML 2022]Sublinear-Time Clustering Oracle for Signed Graphs](http://www.mshxw.com/aiimages/31/1030003.png "论文阅读笔记：[ICML 2022]Sublinear-Time Clustering Oracle for Signed Graphs")
偏DB的模型，在无符号图的聚类算法基础上，为符号图优化了许多定义。
动机已有模型能在符号图里找到近乎平衡的，很少和外部联系的子图。文中也称其为polarized。他们的弊端时需要全局地处理图并区分所有点。一方面，超大图难处理，一方面，一些涉及隐私地图难以得到完整的图。
好在，一般我们只要知道少量点的信息，或者判断两个点是否属于一个社区，而在隐私图中，通过类似随机游走的方式依然可以挖掘邻居信息。
和无符号图算法的比较
- 无符号图直接随机游走就可以被困于社区内，但有符号图不行。论文将图分为两部分解决。此外，无符号图来说，直接embedding就容易让同一个社区的有相似特征，论文对符号图做了针对性优化，为每个社区设定两个相反的中心
- 无符号图一般会考虑L2距离判断两点相似度，但论文已经给符号图做了俩相反中心，所以需要同时判断两种L2距离： Δ ~ u , v : = m i n { ∣ ∣ m u − m v ∣ ∣ 2 2 , ∣ ∣ m u + m v ∣ ∣ 2 2 } tilde{Delta}_{u,v}:=min{||m_u-m_v||^2_2, ||m_u+m_v||^2_2} Δ~u,v:=min{∣∣mu−mv∣∣22,∣∣mu+mv∣∣22}。前者小表示两点属于簇的同一部分，后者小则是不同部分，两个都不小则不属于同一个簇。
- 符号图的簇结构不好直接表示，就新定义了一个表示方式
符号图：
G
=
(
V
,
E
,
σ
)
G=(V,E,sigma)
G=(V,E,σ)，度：
d
G
(
u
)
d_G(u)
dG(u)，子图
S
⊆
V
S subseteq V
S⊆V，体积：
V
o
l
G
(
S
)
=
σ
u
∈
S
d
G
(
v
)
{rm Vol}_G(S)=sigma_{u in S}d_G(v)
VolG(S)=σu∈SdG(v)
图分成两部分：
V
1
,
V
2
⊆
V
,
E
(
V
1
,
V
2
)
=
{
(
u
,
v
)
∈
E
:
u
∈
V
1
,
v
∈
V
2
}
V_1, V_2 subseteq V, E(V_1, V_2) = {(u,v) in E: u in V_1, v in V_2}
V1,V2⊆V,E(V1,V2)={(u,v)∈E:u∈V1,v∈V2}。这两部分不相交时，可以认为他们是
V
V
V的sub-bipartition。
符号二部率：
β
G
(
V
1
,
V
2
)
:
=
e
G
(
V
1
,
V
2
)
V
o
l
G
(
V
1
,
V
2
)
beta_G(V_1, V_2) := frac{e_G(V_1, V_2)}{{rm Vol}_G(V1, V2)}
βG(V1,V2):=VolG(V1,V2)eG(V1,V2)
其中：
e
G
(
V
1
,
V
2
)
=
2
∣
E
G
+
(
V
1
,
V
2
)
∣
+
∣
E
G
−
(
V
1
)
∣
+
∣
E
G
−
(
V
2
)
∣
+
∣
E
G
(
V
1
∪
V
2
,
V
1
∪
V
2
‾
)
∣
e_G(V1, V2)=2|E^+_G(V1, V2)|+|E^-_G(V_1)|+|E^-_G(V_2)|+|E_G(V_1 cup V_2, overline{V_1 cup V_2})|
eG(V1,V2)=2∣EG+(V1,V2)∣+∣EG−(V1)∣+∣EG−(V2)∣+∣EG(V1∪V2,V1∪V2)∣
也就是说，分子是两倍的两部分相连正边数+两部分点各自的负边数+两部分和外部的连接数。分母是两部分所有点的度之和。
β
G
beta_G
βG越小，两部分的负边越少，两边几乎都是负边连接，与外界联系越少，
G
[
V
1
∪
V
2
]
G[V_1 cup V_2]
G[V1∪V2]越接近平衡。
对于子图
U
⊆
V
U subseteq V
U⊆V而言，
β
G
(
U
)
beta_G(U)
βG(U)就是在里面找到
V
1
,
V
2
V_1, V_2
V1,V2，使得
β
G
(
U
)
beta_G(U)
βG(U)最小，这个值就是最后的值。
当且仅当它为0时
U
U
U才是平衡的。
之后的拉普拉斯矩阵，找出独立的k个U等不赘述
lazy random walks in a sign graph的walk matrix是
W
=
I
+
D
−
1
A
2
W=frac{I+D^{-1}A}{2}
W=2I+D−1A。看来偷懒的概率是50%。
还有个
P
v
t
=
1
v
W
t
P^t_v=1_vW^t
Pvt=1vWt，之后用来制作对应顶点的稀疏向量。
定义内部bipartiteness ratio：
β
i
n
n
e
r
(
G
)
:
=
min
∅
≠
U
⊆
V
:
V
o
l
(
G
)
<
1
2
V
o
l
(
G
)
β
G
(
U
)
beta^{inner}(G) := min_{empty neq U subseteq V: {rm Vol}(G)< frac{1}{2}{rm Vol}(G)}beta_G(U)
βinner(G):=min∅=U⊆V:Vol(G)<21Vol(G)βG(U)
定义
(
k
,
β
i
n
,
β
o
u
t
)
−
c
l
u
s
t
e
r
(k, beta_{in}, beta_{out})-cluster
(k,βin,βout)−cluster表示有k个U，每个U都有
β
G
(
U
i
)
≤
β
o
u
t
,
B
i
n
n
e
r
(
G
[
U
i
]
)
≥
β
i
n
beta_G(U_i) leq beta_{out}, B^{inner}(G[U_i]) geq beta_{in}
βG(Ui)≤βout,Binner(G[Ui])≥βin
in的如果太小说明社区还能细分，out太大说明不够close，有了上下界就可以找到合适的社区了。
但是但凡out小了，in肯定也得小。
文中设定探索邻居的数量（探索的度）
d
>
10
d > 10
d>10，子图中社区的数量
k
≥
1
k ge 1
k≥1，内部分数
β
i
n
∈
(
0
,
1
)
beta_{in} in (0,1)
βin∈(0,1)。
再定义两个额外参数
ϵ
∈
(
0
,
1
)
epsilon in (0,1)
ϵ∈(0,1)、
γ
∈
(
0
,
1
]
gamma in (0,1]
γ∈(0,1]。
得到一个整数
n
≥
1800
k
2
log
(
k
)
γ
ϵ
n ge frac{1800k^2log(k)}{gamma^{epsilon}}
n≥γϵ1800k2log(k)，而
n
=
∣
V
∣
n=|V|
n=∣V∣，图中最大的度也不超过是
d
d
d。
设定
β
o
u
t
<
ϵ
β
i
n
2
C
′
log
(
k
)
k
7
d
3
log
(
n
)
beta_{out} < frac{epsilon beta^2_{in}}{C^{'}log(k)k^7d^3log(n)}
βout
具体实现时使用了lazy signed random walk。每走一步都乘上符号，停下的就不乘。每一步都是等概率选择一个邻居。
获取起点
u
u
u的稀疏向量（特征向量）
m
u
∈
R
m
m_u in mathbb{R}^m
mu∈Rm，可证明它近似于
p
u
t
D
−
1
/
2
p^t_uD^{-1/2}
putD−1/2，其实就是半归一的邻接情况。
这样做
R
R
R次游走，如果停在正符号就设为
m
u
+
(
v
)
=
∣
{
i
:
v
i
=
v
,
s
i
=
+
}
∣
R
m^+_u(v)=frac{|{i:v_i=v,s_i=+}|}{R}
mu+(v)=R∣{i:vi=v,si=+}∣，不然就是
m
u
−
(
v
)
=
∣
{
i
:
v
i
=
v
,
s
i
=
−
}
∣
R
m^-_u(v)=frac{|{i:v_i=v,s_i=-}|}{R}
mu−(v)=R∣{i:vi=v,si=−}∣，最终
m
u
=
(
m
u
+
−
m
u
−
)
D
−
1
/
2
m_u=(m^+_u-m^-_u)D^{-1/2}
mu=(mu+−mu−)D−1/2。
判断oracle中两点在一个簇中的可能：
Δ
u
v
:
=
min
{
∣
∣
p
u
t
D
−
1
/
2
−
p
v
t
D
−
1
/
2
∣
∣
2
2
,
∣
∣
p
u
t
D
−
1
/
2
+
p
v
t
D
−
1
/
2
∣
∣
2
2
}
Delta_{uv}:=min{||p^t_uD^{-1/2}-p^t_vD^{-1/2}||^2_2,||p^t_uD^{-1/2}+p^t_vD^{-1/2}||^2_2}
Δuv:=min{∣∣putD−1/2−pvtD−1/2∣∣22,∣∣putD−1/2+pvtD−1/2∣∣22}
当
u
,
v
u,v
u,v属于同一个簇，则这个数就得很小，不然就很大。由于算法没法得到
p
p
p，所以得有一个近似的值
δ
u
v
delta_{uv}
δuv。
定义
Δ
u
v
=
m
i
n
{
Y
u
u
+
Y
v
v
−
2
Y
u
v
,
Y
u
u
+
Y
v
v
+
2
Y
u
v
}
Delta_{uv}=min{Y_{uu}+Y_{vv}-2Y_{uv}, Y_{uu}+Y_{vv}+2Y_{uv}}
Δuv=min{Yuu+Yvv−2Yuv,Yuu+Yvv+2Yuv}，其中
Y
a
b
=
⟨
p
a
t
D
−
1
/
2
,
p
b
t
D
−
1
/
2
⟩
Y_{ab}= left langle p^t_aD^{-1/2},p^t_bD^{-1/2} right rangle
Yab=⟨patD−1/2,pbtD−1/2⟩
本质上就是迭代随机游走获得路径符号信息近似获取特征。
定义
X
a
b
=
E
S
T
D
O
T
P
R
O
B
(
a
,
b
)
X_{ab}={rm ESTDOTPROB}(a,b)
Xab=ESTDOTPROB(a,b)，则
δ
u
v
=
min
{
X
u
u
+
X
v
v
−
2
X
u
v
，
X
u
u
+
X
v
v
+
2
X
u
v
}
delta_{uv}=min{X_{uu}+X_{vv}-2X_{uv}，X_{uu}+X_{vv}+2X_{uv}}
δuv=min{Xuu+Xvv−2Xuv，Xuu+Xvv+2Xuv}。
文中认为
δ
u
v
<
1
2
d
n
delta_{uv} < frac{1}{2dn}
δuv<2dn1时认为这个值够小。
原文：https://proceedings.mlr.press/v162/neumann22a.html
