Sutskever 30 #19:消息一跳一跳地传,传多了整张图糊成一个点
一张随机树,二十来个节点,其中一个是源点,身上藏着一个 bit。其余节点身上也各有一个 bit,全是噪声。任务只有一句话:每个节点都要报出源点那个 bit。 我先拿一个只看自己特征的逐节点分类器跑了一遍。它在源点上 100% 正确——源点带着标记,那个 bit 本来就在它自己手里——在其余每一个节点上,0.501。非源点身上那个 bit 是我特意撒的噪声,跟答案统计独立,所以一个看不见邻居的网络在这些位置上能做的最好的事就是抛硬币。这道题被设计成必须用图:源点的值只能沿着边一格一格爬到别人那里。 于是问题变成,一轮消息传递到底能把这个 bit 带多远。 一轮消息传递,正好一条边 Gilmer 他们 2017 年那篇 Neural Message Passing for Quantum Chemistry 干的事,是把之前一堆各叫各名字的图网络(GG-NN、GCN、interaction networks……)收进同一个抽象里:每个节点先收邻居发来的 message,把它们 aggregate 成一个向量,再拿这个向量 update 自己的状态,跑几轮之后 readout 出图级或节点级的预测。我把它扒到只剩骨头,一轮长这样: $$h_v' = \tanh\!\Big(W_s\, h_v + W_n \sum_{w \in N(v)} \hat A_{vw}\, h_w + b\Big)$$h_v 是节点 v 的隐状态,求和跑遍它的邻居, 是归一化后的邻接矩阵(下面会细说)。关键在求和那一项:一个节点这一轮只能拿到它直接邻居的状态。所以源点的信息每过一轮只能往外渗一跳。要让距离 d 的节点知道源点的值,至少得跑 d 轮。 这跟 #18 是同一面墙,只是从序列搬到了图上:那边是感受野,一维卷积每层把视野撑大固定几格;这边是跳数,每轮消息传递把视野撑大一跳。把训好的网络按节点到源点的图距离分桶,逐桶看准确率: R=1 的网络在距离 1 以内全对,距离 2 起掉到 0.5;R=2 多撑一格,距离 3 起掉下去;R=3 再多一格。三条断崖整整齐齐,各自落在自己的跳数上。桶内数字是 R=1 视野内 1.000 / 视野外 0.503,R=2 是 1.000 / 0.496,R=3 是 0.997 / 0.483。 ...