nips 2021
好久没读论文了，面向未来组会读一篇，读论文和写代码各有各的痛只能说。
这篇是做图压缩的，感觉挺有意思的任务，也知道了些新概念，直接从model的framework部分入手讲起。图压缩是把一个图压缩成一串二进制数字。模型名字叫PnC，具体下来分三个步骤。
1. Partitioning
就是把一个图G分割成子图H和C。比如下面图这样的，红的就是C，其他三种就是H。
2. Graph Dictionary
这一步是把上一步得到的频繁出现的H放到字典D里。
其中a是subgraph压缩成的atom。注意这里是针对一张图的，所以根据这个D可以给出一个图的压缩，称为description。作者在前文提到这个压缩模型重点在长度L上。因为编码界著名的KM不等式，这个不等式作者把它等价为了概率分布。式子的意思就是对于一个空间中很多个图G，有：
满足等号叫这个长度complete，反之代表长度是冗余的。
回到字典的问题。想要将subgraph表示成合适的atom，就要找到合适的长度。当a所在的空间足够大时：
L_null是根据ER随机图模型推出来的。n_max是节点数量上界。
3. Graph Encoding
要求编码之后的码需要解码之后还原唯一的图。之前提过概率分布与长度有关联。子图有两种，字典中的和不在字典中的，用b表示。φ是可训练参数，q是概率分布。
最后，对于一个图G的L：
最终的目标函数：
其中L和q的关系为：
。
读完发现是挺有意思，但感觉对自己的工作帮助不大，概率部分还是不够精通。学到了一点新概念比如ER随机图，但似乎还是用不上，哈哈。
若有收获，就点个赞吧
0 人点赞
