图表示学习|《Graph Representation Learning》笔记 Chapter5 机器学习|图论|图嵌入|图计算

系列文章
《Graph Representation Learning》笔记 Chapter2
《Graph Representation Learning》笔记 Chapter3
《Graph Representation Learning》笔记 Chapter4

目录

Permutation invariance and equivariance
Neural Message Passing
- Overview of the Message Passing Framework
- The Basic GNN
- Node vs. graph-level equation
- Message Passing with Self-loops
Generalized Neighborhood
- Neighborhood Normalization
- - Graph convolutional network(GCNs)
- Set Aggregators
- - Set pooling
  - Janossy pooling
- Neighborhood Attention
Generalized Update Methods
- Over-smoothing and neighbourhood influence
- Concatenation and Skip-Connections
- Gated Updates
- Jumping Knowledge Connections
Edge Features and Multi-relational GNNs
- Relational Graph Neural Networks
- - Parameter sharing
- Attention and Feature Concatenation
Graph Pooling
- Set pooling approaches
- Graph coarsening approaches
Generalized Message Passing

Permutation invariance and equivariance 为了生成整张图的 embedding ，我们可以将邻接矩阵展平后输入到多层感知机 (MLP) 中
z G = M L P ( A [ 1 ] ⊕ A [ 2 ] ⊕ . . . ⊕ A [ ∣ V ∣ ] ) z_{\mathcal{G}} = MLP(A[1] \oplus A[2] \oplus ... \oplus A[|\mathcal{V}|]) zG?=MLP(A[1]⊕A[2]⊕...⊕A[∣V∣])
其中，A [ i ] ∈ R ∣ V ∣ A[i] ∈ R^{|\mathcal{V}|} A[i]∈R∣V∣ 表示邻接矩阵的第i i i 行，使用⊕ \oplus ⊕ 代表向量拼接。
这种方法高度依赖于邻接矩阵中节点的顺序，我们所期望的模型需要具有排列不变性或排列相等性，这两种性质可用数学公式表示为
f ( P A P T ) = f ( A ) （排列不变性） f ( P A P T ) = P f ( A ) （排列相等性） \begin{aligned} f(PAP^T) = f(A) &（排列不变性）\\ f(PAP^T) = Pf(A) &（排列相等性） \end{aligned} f(PAPT)=f(A)f(PAPT)=Pf(A)?（排列不变性）（排列相等性）?
其中，f f f 为我们所期望的模型，P P P 为排列矩阵， P A P T PAP^T PAPT 表示将邻接矩阵先进行行变换再进行相同规则的列变换，即变换节点在邻接矩阵中所处的顺序。
Neural Message Passing 我们将讨论图神经网络 (GNN) 结构如何用于产生子图和整图的 embeddings 。
Overview of the Message Passing Framework GNN 在每次信息传递迭代时，每个 hidden embeddingh u ( k ) , u ∈ V h_u^{(k)}, u ∈ \mathcal{V} hu(k)?,u∈V 被更新通过聚合u u u 的邻域N ( u ) \mathcal{N}(u) N(u) 的信息，如下图所示

图表示学习|《Graph Representation Learning》笔记 Chapter5

文章图片

它的数学表达示为
h u ( k + 1 ) = U P D A T E ( k ) ( h u ( k ) , A G G R E G A T E ( k ) ( { h v ( k ) , ? v ∈ N ( u ) } ) ) = U P D A T E ( k ) ( h u ( k ) , m N ( u ) ( k ) ) \begin{aligned} h_u^{(k+1)} &= UPDATE^{(k)}(h_u^{(k)}, AGGREGATE^{(k)}(\{h_v^{(k)}, \forall{v} ∈ \mathcal{N}(u)\})) \\ &= UPDATE^{(k)}(h_u^{(k)}, m_\mathcal{N(u)}^{(k)}) \end{aligned} hu(k+1)??=UPDATE(k)(hu(k)?,AGGREGATE(k)({hv(k)?,?v∈N(u)}))=UPDATE(k)(hu(k)?,mN(u)(k)?)?
其中，U P D A T E UPDATE UPDATE 和A G G R E G A T E AGGREGATE AGGREGATE 是任意的可微函数，m N ( u ) m_\mathcal{N(u)} mN(u)? 是节点u u u 邻域N ( u ) \mathcal{N}(u) N(u) 的信息聚合。
在K K K 次迭代（信息传递）后，我们可以用最后一层的输出来定义每个节点的 embeddings
z u = h u ( K ) , ? u ∈ V z_u = h_u^{(K)}, \forall{u} ∈ \mathcal{V} zu?=hu(K)?,?u∈V
The Basic GNN 基本 GNN 信息传递被定义为
h u ( k ) = σ ( W s e l f ( k ) h u ( k ? 1 ) + W n e i g h ( k ) ∑ v ∈ N ( u ) h v ( k ? 1 ) + b ( k ) ) h_u^{(k)} = σ(W_{self}^{(k)}h_u^{(k-1)} + W_{neigh}^{(k)}\sum_{v ∈ \mathcal{N}(u)}h_v^{(k-1)} + b^{(k)}) hu(k)?=σ(Wself(k)?hu(k?1)?+Wneigh(k)?v∈N(u)∑?hv(k?1)?+b(k))
其中,W s e l f ( k ) , W n e i g h ( k ) ∈ R d ( k ) × d ( k ? 1 ) W_{self}^{(k)}, W_{neigh}^{(k)} ∈ \mathbb{R}^{d^{(k)} × d^{(k-1)}} Wself(k)?,Wneigh(k)?∈Rd(k)×d(k?1) 是可训练的参数矩阵，σ σ σ 表示非线性函数。为了表述简洁，下文中的偏置b ( k ) ∈ R d ( k ) b^{(k)} ∈ \mathbb{R}^{d^{(k)}} b(k)∈Rd(k) 会省略，但不可忽视。
定义U P G A T E UPGATE UPGATE 和A G G R E G A T E AGGREGATE AGGREGATE 函数
m N ( u ) = A G G R E G A T E ( { h v , ? v ∈ N ( u ) } ) = ∑ v ∈ N ( u ) h v U P D A T E ( h u , m N ( u ) ) = σ ( W s e l f h u + W n e i g h m N ( u ) ) m_{\mathcal{N}(u)} = AGGREGATE(\{h_v, \forall{v} ∈ \mathcal{N}(u)\}) = \sum_{v ∈ \mathcal{N}(u)}h_v \\ UPDATE(h_u, m_\mathcal{N(u)}) = σ(W_{self}h_u + W_{neigh}m_{\mathcal{N}(u)}) mN(u)?=AGGREGATE({hv?,?v∈N(u)})=v∈N(u)∑?hv?UPDATE(hu?,mN(u)?)=σ(Wself?hu?+Wneigh?mN(u)?)
同样为了表述简洁，我们省略了式中的上角标。
Node vs. graph-level equation 我们可以简洁地定义整图级别的 GNN 模型
H ( t ) = σ ( A H ( k ? 1 ) W n e i g h k + H ( k ? 1 ) W s e l f ( k ) ) H^{(t)} = σ(AH^{(k-1)}W_{neigh}^{k} + H^{(k-1)}W_{self}^{(k)}) H(t)=σ(AH(k?1)Wneighk?+H(k?1)Wself(k)?)
式中H ( k ) ∈ R ∣ V ∣ × d H^{(k)} ∈ \mathbb{R}^{|V| × d} H(k)∈R∣V∣×d 表示第 t 层 GNN 输出的节点 embeddings 的集合（按行排列）。
Message Passing with Self-loops 为了简化信息传播方法，我们加入了自循环机制，定义为
h u ( k ) = A G G R E G A T E ( { h v ( k ? 1 ) , ? v ∈ N ( u ) ∪ { u } } ) ) h_u^{(k)} = AGGREGATE(\{h_v^{(k-1)}, \forall{v} ∈ \mathcal{N}(u) \cup \{u\} \})) hu(k)?=AGGREGATE({hv(k?1)?,?v∈N(u)∪{u}}))
现在， AGGREGATE 的输入变为了集合N ( u ) ∪ { u } \mathcal{N}(u) \cup \{u\} N(u)∪{u} ，不需要额外定义U P D A T E UPDATE UPDATE 函数，这中方法减轻了过拟合现象，但是节点邻域的信息与该节点的信息在聚合时并没有区分开。
对于整图来说，自循环机制相当于将W s e l f W_{self} Wself? 和W n e i g h W_{neigh} Wneigh? 的参数进行共享，表达式变为
H ( t ) = σ ( ( A + I ) H ( t ? 1 ) W ( t ) ) H^{(t)} = σ((A+I)H^{(t-1)}W^{(t)}) H(t)=σ((A+I)H(t?1)W(t))
Generalized Neighborhood Neighborhood Normalization 当不同节点所对应的邻域节点数差距过大时，会导致数值的不稳定以及优化困难。一个解决方法是通过节点的 degrees 来标准化A G G R E G A T E AGGREGATE AGGREGATE 操作，如下所示
m N ( u ) = ∑ v ∈ N ( u ) h v ∣ N ( u ) ∣ m_{\mathcal{N}(u)} = \frac{\sum_{v ∈ \mathcal{N}(u)}h_v}{|\mathcal{N}(u)|} mN(u)?=∣N(u)∣∑v∈N(u)?hv??
下面的对称标准化也能起到不错的效果
m N ( u ) = ∑ v ∈ N ( u ) h v ∣ N ( u ) ∣ ∣ N ( v ) ∣ m_{\mathcal{N}(u)} = \sum_{v ∈ \mathcal{N}(u)} \frac{h_v}{\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}} mN(u)?=v∈N(u)∑?∣N(u)∣∣N(v)∣ ?hv??
Graph convolutional network(GCNs)
GCN 模型定义信息传递函数为
h u ( k ) = σ ( W ( k ) ∑ v ∈ N ( u ) ∪ { u } h v ∣ N ( u ) ∣ ∣ N ( v ) ∣ ) h_u^{(k)} = σ(W^{(k)}\sum_{v ∈ \mathcal{N}(u) \cup \{u\} } \frac{h_v}{\sqrt{|\mathcal{N}(u)||\mathcal{N}(v)|}}) hu(k)?=σ(W(k)v∈N(u)∪{u}∑?∣N(u)∣∣N(v)∣ ?hv??)
Set Aggregators Set pooling
我们需要基于上文提到的排列不变性来定义 AGGREGATE 函数， Zaheer 定义了如下函数
m N ( u ) = M L P θ ( ∑ v ∈ N M L P ? ( h v ) ) m_{\mathcal{N}(u)} = MLP_θ(\sum_{v ∈ N}MLP_{\phi}(h_v)) mN(u)?=MLPθ?(v∈N∑?MLP??(hv?))
其中，M L P θ MLP_θ MLPθ? 代表有着可训练参数θ θ θ 的多层感知机。
Janossy pooling
Janossy pooling 计算所有可能的排列输入产生的结果进行平均
m N ( u ) = M L P θ ( 1 ∣ Π ∣ ∑ π i ∈ Π ρ ? ( h v 1 , h v 2 , . . . , h v ∣ N ( u ) ∣ ) π i ) m_{\mathcal{N}(u)} = MLP_θ(\frac{1}{|\Pi|} \sum_{\pi_i ∈ \Pi} ρ_{\phi}(h_{v_1}, h_{v_2}, ..., h_{v_{|\mathcal{N}(u)|}})_{\pi_i}) mN(u)?=MLPθ?(∣Π∣1?πi?∈Π∑?ρ??(hv1??,hv2??,...,hv∣N(u)∣??)πi??)
其中，Π \Pi Π 表示排列函数π i \pi_i πi? 的集合，ρ ? ρ_{\phi} ρ?? 为序列输入的函数，如 LSTM 。
Neighborhood Attention 第一个引入注意力机制的GNN模型为 Graph Attention Network(GAT) ，它使用注意力权重来聚合邻域信息
m N ( u ) = ∑ v ∈ N ( u ) α u , v h v m_{\mathcal{N}(u)} = \sum_{v ∈ \mathcal{N}(u)} α_{u, v}h_v \\ mN(u)?=v∈N(u)∑?αu,v?hv?
其中，α u , v α_{u, v} αu,v? 代表注意力权重。有的注意力权重被定义为
α u , v = e x p ( a T [ W h u ⊕ W h v ] ) ∑ v ′ ∈ N ( u ) e x p ( a T [ W h u ⊕ W h v ′ ] ) α_{u, v} = \frac{exp(a^T[Wh_u \oplus Wh_v])}{\sum_{v' ∈ \mathcal{N}(u)} exp(a^T[Wh_u \oplus Wh_{v'}])} αu,v?=∑v′∈N(u)?exp(aT[Whu?⊕Whv′?])exp(aT[Whu?⊕Whv?])?
其中，a a a 是一个可训练的注意力向量，W W W 是一个可训练的矩阵，⊕ \oplus ⊕ 代表向量拼接操作。
令一种流行的注意力权重被定义为
α u , v = e x p ( h u T W h v ) ∑ v ′ ∈ N ( u ) e x p ( h u T W h v ′ ) α_{u, v} = \frac{exp(h_u^TWh_v)}{\sum_{v' ∈ \mathcal{N}(u)} exp(h_u^TWh_{v'})} αu,v?=∑v′∈N(u)?exp(huT?Whv′?)exp(huT?Whv?)?
有人使用 MLPs 来计算注意力权重
α u , v = e x p ( M L P ( h u , h v ) ) ∑ v ′ ∈ N ( u ) e x p ( M L P ( h u , h v ′ ) ) α_{u, v} = \frac{exp(MLP(h_u, h_v))}{\sum_{v' ∈ \mathcal{N}(u)} exp(MLP(h_u, h_{v'}))} αu,v?=∑v′∈N(u)?exp(MLP(hu?,hv′?))exp(MLP(hu?,hv?))?
其中，M L P MLP MLP 被限制为一个标量输出。
有人将 transformer 结构引入 GNN ，这种方法使用不同参数的注意力层计算K K K 个不同的注意力权重α u , v , k α_{u, v, k} αu,v,k? ，在信息A G G R E G A T E AGGREGATE AGGREGATE 时，先使用这些权重进行信息 transform ，在将变化后的信息堆积在一起，表达式如下
m N ( u ) = [ a 1 ⊕ a 2 ⊕ . . . ⊕ a K ] a k = W i ∑ v ∈ N ( u ) α u , v , k h v m_{\mathcal{N}(u)} = [a_1 \oplus a_2 \oplus ... \oplus a_K] \\ a_k = W_i \sum_{v ∈ \mathcal{N}(u)} α_{u, v, k} h_v mN(u)?=[a1?⊕a2?⊕...⊕aK?]ak?=Wi?v∈N(u)∑?αu,v,k?hv?
Generalized Update Methods Over-smoothing and neighbourhood influence 在 GNN 中，对于任意节点对，我们可以通过雅可比矩阵量化u u u 对v v v 的影响
I K ( u , v ) = 1 T ( δ h v ( K ) δ h u ( 0 ) ) 1 I_K(u, v) = \bm1^T(\frac{δh_v^{(K)}}{δh_u^{(0)}}) \bm1 IK?(u,v)=1T(δhu(0)?δhv(K)??)1
其中，1 \bm1 1 为全1向量。
对于自循环方法来说，信息A G G R E G A T E AGGREGATE AGGREGATE 函数表示如下
A G G R E G A T E ( { h v , ? v ∈ N ( u ) ∪ { u } } ) = 1 f n ( ∣ N ( u ) ∪ { u } ∣ ) ∑ v ∈ N ( u ) ∪ { u } h v AGGREGATE(\{h_v, \forall{v} ∈ \mathcal{N}(u) \cup \{u\} \}) = \frac{1}{f_n(|\mathcal{N}(u) \cup \{u\}|)} \sum_{v ∈ \mathcal{N}(u) \cup \{u\} h_v} AGGREGATE({hv?,?v∈N(u)∪{u}})=fn?(∣N(u)∪{u}∣)1?v∈N(u)∪{u}hv?∑?
其中，f : R + → R + f: \mathbb{R}^+ \rightarrow \mathbb{R}^+ f:R+→R+ 是标准化函数。
我们知道
I K ( u , v ) ∝ p G , K ( u ∣ v ) I_K(u, v) \propto p_{\mathcal{G}, K}(u | v) IK?(u,v)∝pG,K?(u∣v)
其中，p G , K ( u ∣ v ) p_{\mathcal{G}, K}(u | v) pG,K?(u∣v) 代表节点u u u 以长度为K K K 的随机路径移动到节点v v v 的概率。当K → ∞ K \rightarrow ∞ K→∞ 时，对于任意节点对，p G , K ( u ∣ v ) p_{\mathcal{G}, K}(u | v) pG,K?(u∣v) 趋于相同，导致邻域信息丢失，即出现过平滑现象。
Concatenation and Skip-Connections 将基本U P D A T E UPDATE UPDATE 的输出与节点的上一层 embedding 拼接，可以在信息传递中保持更多的节点信息
U P D A T E c o n c a t ( h u , m N ( u ) ) = [ U P D A T E b a s e ( h u , m N ( u ) ) ⊕ h u ] UPDATE_{concat}(h_u, m_{\mathcal{N}(u)}) = [UPDATE_{base}(h_u, m_{\mathcal{N}(u)}) \oplus h_u] UPDATEconcat?(hu?,mN(u)?)=[UPDATEbase?(hu?,mN(u)?)⊕hu?]
除了拼接，其他方式的 skip-connections 也可被使用，比如说线性插值方法，如下所示
U P D A T E i n t e r p o l a t e ( h u , m N ( u ) ) = α 1 ° U P D A T E b a s e ( h u , m N ( u ) ) + α 2 ⊙ h u UPDATE_{interpolate}(h_u, m_{\mathcal{N}(u)}) = \alpha_1 \circ UPDATE_{base}(h_u, m_{\mathcal{N}(u)}) + \alpha_2 \odot h_u UPDATEinterpolate?(hu?,mN(u)?)=α1?°UPDATEbase?(hu?,mN(u)?)+α2?⊙hu?
其中，α 1 , α 2 ∈ [ 0 , 1 ] d \alpha_1, \alpha_2 ∈ [0, 1]^d α1?,α2?∈[0,1]d 为门控向量，α 2 = 1 ? α 1 \alpha_2 = 1 - \alpha_1 α2?=1?α1? ，° \circ ° 代表 Hadamard 积。
Gated Updates 我们也可以通过观测值使用门控循环单元( gated recurrent unit, GRU )来更新隐藏状态
h u ( k ) = G R U ( h u ( k ? 1 ) , m N ( u ) ( k ) ) h_u^{(k)} = GRU(h_u^{(k-1)}, m_{\mathcal{N(u)}}^{(k)}) hu(k)?=GRU(hu(k?1)?,mN(u)(k)?)
Jumping Knowledge Connections 简单的在信息传递中利用每层的节点表示也可以提升最终的节点表示z u z_u zu?
z u = f J K ( h u ( 0 ) ⊕ h u ( 1 ) ⊕ . . . ⊕ h u ( K ) ) z_u = f_{JK}(h_u^{(0)} \oplus h_u^{(1)} \oplus ... \oplus h_u^{(K)}) zu?=fJK?(hu(0)?⊕hu(1)?⊕...⊕hu(K)?)
其中，f J K f_{JK} fJK? 为任意函数。
Edge Features and Multi-relational GNNs Relational Graph Neural Networks aggregation 方法可以通过在每种关系上指定一个单独的转移矩阵来适应多关系情况
m N ( u ) = ∑ τ ∈ R ∑ v ∈ N τ ( u ) W τ h v f n ( N ( u ) , N ( v ) ) m_{\mathcal{N}(u)} = \sum_{\tau ∈ \mathcal{R}} \sum_{v ∈ \mathcal{N}_{\tau}(u)} \frac{W_{\tau}h_v}{f_n(\mathcal{N}(u), \mathcal{N}(v))} mN(u)?=τ∈R∑?v∈Nτ?(u)∑?fn?(N(u),N(v))Wτ?hv??
其中，f n f_n fn? 是一个标准化函数，R \mathcal{R} R 为存在的关系，W τ W_{\tau} Wτ? 为关系矩阵。
Parameter sharing
上述方法的参数过多，所以有人提出了共享参数的方法
W τ = ∑ i = 1 b α i , τ B i W_{\tau} = \sum_{i=1}^b \alpha_{i, \tau} B_i Wτ?=i=1∑b?αi,τ?Bi?
关系矩阵W τ W_{\tau} Wτ? 被定义为 b 个基本矩阵B 1 , . . . , B b B_1, ..., B_b B1?,...,Bb? 的线性叠加，权重为α 1 , τ , . . . , α b , τ \alpha_{1, \tau}, ..., \alpha_{b, \tau} α1,τ?,...,αb,τ? 。
aggregate 函数表示为
m N ( u ) = ∑ τ ∈ R ∑ v ∈ N τ ( u ) α τ × B × h v f n ( N ( u ) , N ( v ) ) m_{\mathcal{N}(u)} = \sum_{\tau ∈ \mathcal{R}} \sum_{v ∈ \mathcal{N}_{\tau}(u)} \frac{\alpha_{\tau} \times \mathcal{B} \times h_v}{f_n(\mathcal{N}(u), \mathcal{N}(v))} mN(u)?=τ∈R∑?v∈Nτ?(u)∑?fn?(N(u),N(v))ατ?×B×hv??
其中，B = ( B 1 , . . . , B b ) \mathcal{B} = (B_1, ..., B_b) B=(B1?,...,Bb?) 为堆积所有基本矩阵B i B_i Bi? 的张量，α τ = ( α 1 , τ , . . . , α b , τ ) \alpha_{\tau} = (\alpha_{1, \tau}, ..., \alpha_{b, \tau}) ατ?=(α1,τ?,...,αb,τ?) 为关系τ \tau τ 中的权重向量。
Attention and Feature Concatenation 定义一个新的 aggregation 函数
m N ( u ) = A G G R E F A T E b a s e ( { h v ⊕ e ( u , τ , v ) , ? v ∈ N ( u ) } ) m_{\mathcal{N}(u)} = AGGREFATE_{base}(\{ h_v \oplus e_{(u, \tau, v)}, \forall v ∈ \mathcal{N}(u) \}) mN(u)?=AGGREFATEbase?({hv?⊕e(u,τ,v)?,?v∈N(u)})
其中，e ( u , τ , v ) e_{(u, \tau, v)} e(u,τ,v)? 代表边缘( u , τ , v ) (u, \tau, v) (u,τ,v) 的特征向量。
Graph Pooling Set pooling approaches 我们想要设计一个能将节点嵌入 { z 1 , z ∣ V ∣ } \{z_1, z_{|V|}\} {z1?,z∣V∣?} 映射至图嵌入z G z_\mathcal{G} zG? 的池化函数f p f_p fp? 。
第一种方法是简单的取节点嵌入的和或平均
z G = ∑ v ∈ V z v f n ( ∣ V ∣ ) z_{\mathcal{G}} = \frac{\sum_{v ∈ \mathcal{V}}z_v}{f_n(|\mathcal{V}|)} zG?=fn?(∣V∣)∑v∈V?zv??
第二种方法结合了 LSTM 和注意力机制，需要迭代t = 1 , . . . , T t=1, ..., T t=1,...,T 步
q t = L S T M ( o t ? 1 , q t ? 1 ) e v , t = f a ( z v , q t ) , ? v ∈ V a v , t = e x p ( e v , t ) ∑ u ∈ V e u , t , ? v ∈ V o t = ∑ v ∈ V a v , t z v q_t = LSTM(o_{t-1}, q_{t-1}) \\ e_{v, t} = f_a(z_v, q_t), \forall v ∈ \mathcal{V} \\ a_{v, t} = \frac{exp(e_{v, t})}{\sum_{u ∈ \mathcal{V}}e_{u, t}}, \forall v ∈ \mathcal{V} \\ o_t = \sum_{v ∈ \mathcal{V}} a_{v, t}z_v qt?=LSTM(ot?1?,qt?1?)ev,t?=fa?(zv?,qt?),?v∈Vav,t?=∑u∈V?eu,t?exp(ev,t?)?,?v∈Vot?=v∈V∑?av,t?zv?
其中，q t q_t qt? 向量代表第t t t 轮的查询向量，由上一轮的观测向量和查询向量计算而成。f a : R d × R d → R f_a: \mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R} fa?:Rd×Rd→R 代表注意力函数，e v , t e_{v, t} ev,t? 代表第t t t 轮的注意力分数，将注意力分数规则化后变为a v , t a_{v, t} av,t?。最终，将节点嵌入加权相加后得到观测向量。q 0 q_0 q0? 和o 0 o_0 o0? 初始化为全零向量，整图嵌入表示为
z G = o 1 ⊕ o 2 ⊕ . . . ⊕ o T z_{\mathcal{G}} = o_1 \oplus o_2 \oplus ... \oplus o_T zG?=o1?⊕o2?⊕...⊕oT?
Graph coarsening approaches 【图表示学习|《Graph Representation Learning》笔记 Chapter5】假定我们由一些聚类函数将所有节点分配到c c c 个簇中
f c → G × R ∣ V ∣ × d → R + ∣ V ∣ × c S = f c ( G , Z ) f_c \rightarrow \mathcal{G} \times \mathbb{R}^{|V| \times d} \rightarrow \mathbb{R}^{+|V| \times c} \\ S = f_c(\mathcal{G}, Z) fc?→G×R∣V∣×d→R+∣V∣×cS=fc?(G,Z)
其中，S [ u , i ] ∈ R + S[u, i] ∈ \mathbb{R}^+ S[u,i]∈R+ 代表节点u u u 和簇i i i 的联系强度。
修改邻接矩阵使其表示簇和簇之间的连接强度
A n e w = S T A S ∈ R + c × c A^{new} = S^TAS ∈ \mathbb{R}^{+c \times c} Anew=STAS∈R+c×c
修改嵌入矩阵使其表示簇嵌入
X n e w = S T X ∈ R c × d X^{new} = S^T X ∈ \mathbb{R} ^{c \times d} Xnew=STX∈Rc×d
每一轮进行迭代，簇会越来越少，最终形成一个充分粗糙的图嵌入
Generalized Message Passing 信息传递还需利用边和整图的信息，传递方式如下所示
h ( u , v ) ( k ) = U P D A T E e d g e ( h ( u , v ) ( k ? 1 ) , h u ( k ? 1 ) , h v ( k ? 1 ) , h G ( k ? 1 ) ) m N ( u ) = A G G R E G A T E n o d e ( { h ( u , v ) ( k ) , ? v ∈ N ( u ) } ) h u ( k ) = U P D A T E n o d e ( h u ( k ? 1 ) , m N ( u ) , h G ( k ? 1 ) ) h G ( k ) = U P D A T E g r a p h ( h G ( k ? 1 ) , { h u ( k ) , ? u ∈ V } , { h ( u , v ) ( k ) , ? ( u , v ) ∈ E } ) h_{(u, v)}^{(k)} = UPDATE_{edge} (h_{(u, v)}^{(k-1)}, h_u^{(k-1)}, h_v^{(k-1)}, h_{\mathcal{G}}^{(k-1)}) \\ m_{\mathcal{N}(u)} = AGGREGATE_{node} (\{ h_{(u, v)}^{(k)}, \forall v ∈ \mathcal{N}(u) \}) \\ h_u^{(k)} = UPDATE_{node} (h_u^{(k-1)}, m_{\mathcal{N}(u)}, h_{\mathcal{G}}^{(k-1)}) \\ h_{\mathcal{G}}^{(k)} = UPDATE_{graph}(h_{\mathcal{G}}^{(k-1)}, \{ h_u^{(k)}, \forall u ∈ \mathcal{V} \}, \{ h_{(u, v)}^{(k)}, \forall (u, v) ∈ \mathcal{E} \}) h(u,v)(k)?=UPDATEedge?(h(u,v)(k?1)?,hu(k?1)?,hv(k?1)?,hG(k?1)?)mN(u)?=AGGREGATEnode?({h(u,v)(k)?,?v∈N(u)})hu(k)?=UPDATEnode?(hu(k?1)?,mN(u)?,hG(k?1)?)hG(k)?=UPDATEgraph?(hG(k?1)?,{hu(k)?,?u∈V},{h(u,v)(k)?,?(u,v)∈E})