作者：gufe_hfding

论文概要

今天的论文是来自上海交大傅洛伊老师团队在INFOCOM 2020上的论文，这篇论文主要是利用了多跳相邻关系来刻画更多的结构信息，使得在Seedless based 匿名中做子图匹配的时候，效率更高，同时利用更多的结构信息。傅老师研究社交网络很多年了，也发表了很多高水平的论文，感觉是望其项背啦。更多傅老师的信息，可以看她的网页：http://www.cs.sjtu.edu.cn/~fu-ly/index.html

论文的引用：

Jiapeng Zhang, Luoyi Fu, Xinbing Wang, Songwu Lu:
De-anonymization of Social Networks: the Power of Collectiveness. INFOCOM 2020: 89-98

论文主要创新

由于无种子的图数据去匿名攻击方法是NP难的，最直观的无种子图数据去您名攻击是对匿名图和辅助图进行全局的子图匹配，使得匹配后的两个图中对应的节点差异性之和最小。搜索的空间过大，每次也仅仅匹配某个节点相邻的节点信息，导致效率不高，信息利用率也比较差。

这篇论文利用了多跳的结构信息，构造了新的多跳的邻接矩阵，并量化对应节点的多跳邻接矩阵的 collective adjacency disagreements（集体邻接矩差异），使得全局的集体邻接矩差异之和最小。

论文的方法确实有效，能够利用更多的结构信息，搜索空间也变小了一些，特别是论文中设计了一个近似算法，能够提高图匹配的效率。

启发

本质上图数据的去匿名攻击就是在考虑如何更加有效地利用更多的结构信息，如果能一次性利用全局性的结构信息，结构信息可以向量化或者标量化更好，就成为了vec2node类似的方法，对节点进行向量化，然后通过匹配两个图的节点的相似性来进行节点匹配，或者子图匹配。并针对两个图的向量匹配之后的图的差异性和最小问题，设计高效的算法进行计算。

我这里能想到的除了用图嵌入的方法，还可以用结构熵构造两个图所有节点的结构熵，使得结构熵差异性最小，就变成了 简单的问题。需要编程实现以下。

即匿名图 G a G_a Ga​和辅助图 G a u G_{au} Gau​中所有的节点的的结构信息构成两个 n n n维向量，两个向量的分量间的差的平方和最小。