Hierarchical Graph Representatio

[DIFFPooLing-NIPS18]

Hierarchical structure

• 学习graph的层次结构，层次表示
• DIFFPOOL为deep gnn的每一层节点学习differentiable cluster assignment（) ，将节点映射到一组cluster，形成下一个gnn层的coarsened input。
• 核心思想是通过提供一个能够区分graph层次节点的pooling操作来得到一个更深，更多层次结构的gnn模型。

DIFFPOOL: differentiable pooling

提供一个可微分的module分层的pooling graph中的节点。

definition

• , where is the adjacency matrix, is the node feature matrix.
• Given a set of labels graphs .
• graph classification: ，即将一个graph映射到一个标签。

Graph Nerual Network

neural message passing：

• 是k层gnn的节点embedding；
• 是一个消息传播函数：依赖于adjacency matrix 和, 比如可以用GraphSAGE, GCN等;
• 初始化： ，输入节点embedding为。

Hierarchical Graph Neural Networks and pooling layer

寻找一个通用的，端到端的区分策略以完成graph的节点分层表示

• 给定一个gnn的输出 and the adjacency matrix ，目标是寻找一中方式可以得到一个新的coarsened graph:包含个节点： 。当前层的输出作为下一层的输入。
• 目标就是需要学习一种pooling策略，这种策略可以泛化到具有不同节点、边的图中，并且能够在推理过程中能适应不同的图结构。

Differentiable Pooling via Learned Assignments

DIFFPOOL方法通过学习gnn节点上的cluster assignment matrix: ，来实现上述目标。

Pooling with an assignment matrix

• 定义第层学到的cluster assignment matrix: ;

• assignment matrix 表示第层的每一个节点到第层的每一个节点(或cluster)的概率.

粗化输入图，生成新的adjacency matrix 和新的embeddings matrix: :

Learning the assignment matrix

• 为第层的输入节点生成新的embedding；
• 表示第层的pooling GNN，生成的是从输入节点到个cluster的概率；
• 的输出位数对应于第层预定义的最大clusters数，是模型的超参数；
• 使用cluster的adjacency matrix 和特征矩阵生成一个assignment matrix .

DIFFPOOL示意图

• 在每一层，运行一个gnn模型：输入 ，
  • 获得节点的embeddings：;
  • cluster assignment matrix：.
• DIFFPOOL操作，得到下一层gnn的输入：.
  • ;
  • .

层次化的gnn加入了pooling层，能够捕捉graph的层次信息。