Page 313 - 《软件学报》2025年第12期

5694 软件学报 2025 年第 36 卷第 12 期


TP = |{t ∈ S 2 (G) : Label λ ◦ Func θ (t) = f (t) = 1}|
 w



T

 N = |{t ∈ S 2 (G) : Label λ ◦ Func θ (t) = f (t) = 0}|
 w



FP = |{t ∈ S 2 (G) : Label λ ◦ Func θ (t) = 1 and f (t) = 0}| w (B2)





FN = |{t ∈ S 2 (G) : Label λ ◦ Func θ (t) = 0 and f (t) = 1}|
 w



 sum = |S 2 (G)| w = TP+TN + FP+ FN
通过定义有:

 TP+ FP

 TP+ FN FP− FN
 −
ERR ≈ =

 sum sum sum
 abs abs
 (B3)
 TP+TN sum− FP− FN


ACC = =

sum sum
所以对于 λ 的不同, Label λ 改变后可能出现 ERR 为 0 的情况, 此时对应着 FP = FN. 同时由于 FP+ FN =
(1− ACC)× sum, 则:


|FP− FN| abs ⩽ |FP| abs +|FN| abs = (1− ACC)× sum

(B4)

 ERR ≈ |FP− FN| abs /sum ⩽ 1− ACC
1− ACC. 这是一个相当宽松的上界: 由于
因此不考虑 S 2 选择所导致的误差时, 模型评估误差 ERR 不会超过
FP,FN ⩾ 0, |FP− FN| abs ⩽ max(FP,FN), 因此仅在 FP 或 FN 为 0 时取得等号.
不等式 (B4) 也证明, 若假设同一模型在不同数据集上, 评估三元组正误的正确判断 ACC 接近定值时, 该模型
评估误差存在上界 1− ACC, 且模型判断三元组正误的正确率 ACC 越高时, 评估误差上界越小, 评估越可靠.
张明韬(2002－), 男, 博士生, 主要研究领域为图 白晓颖(1973－), 女, 博士, 研究员, 博士生导师,
数据分析, 时空数据分析. 主要研究领域为软件工程, 软件测试, 服务计算.

杨国利(1987－), 男, 博士, 助理研究员, CCF 专
业会员, 主要研究领域为复杂网络结构, 图数据
分析.