Sym normalization of adj matrix

Questions
#1

\hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2}
please explain how normalization is carried out. in the code usually,

                degs = graph.in_degrees().float().clamp(min=1)
                norm = th.pow(degs, -0.5)
                norm = norm.to(feat.device).unsqueeze(1)
                feat = feat * norm
#2

The matrix form of GCN update rule is as follows:

H^{(l+1)}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)},

where:

  • H^{(l)}\in\mathbb{R}^{N\times F_l} is the node features after the l-th GCN layer, N is the number of nodes, F_l is the feature size for H^{(l)}. H^{(0)} is the input node features.
  • W^{(l)}\in\mathbb{R}^{F_l\times F_{l+1}} is the learnable weight in the l-th GCN layer.
  • \tilde{A}=A+I, where A is the adjacency matrix.
  • \tilde{D}=\tilde{A}\textbf{1} is the degree matrix corresponding to \tilde{A}, \textbf{1}\in\mathbb{R}^{N\times 1} is a vector whose entries are all 1.

Element-wise, the update rule for a node v is then

H_{v, :}^{(l+1)}=\sum_{u\in\mathcal{N}(v)}\frac{1}{\sqrt{\tilde{d}_u\tilde{d}_{v}}}W^{(l)}H_{u, :}^{(l)}, where \tilde{d}_u=\tilde{D}_{uu}.

degs = graph.in_degrees().float().clamp(min=1)

computes the diagonal of A\textbf{1} (it’s possible that self loops have been added already, which becomes \tilde{A}\textbf{1}). In case there are isolated nodes, it replaces 0-valued entries by 1-valued entries.

norm = th.pow(degs, -0.5)

raises each element in degs to power -\frac{1}{2}, corresponding to \tilde{D}^{-\frac{1}{2}}.

feat = feat * norm

replaces h^{(l)}_u by \frac{1}{\sqrt{degs[u]}}h^{(l)}_u, corresponding to \frac{1}{\sqrt{\tilde{d_u}}}h^{(l)}_u.

#3

Thank you for the detailed answer. :grinning:

What about the

\tilde{D}^{-\frac{1}{2}}\tilde{A}

In the code normalization H^{(l)} with \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}} is

  • calc “norm”
norm = th.pow(graph.in_degrees().float().clamp(min=1), -0.5)
  • normalize by src node
feat = feat * norm
  • graph conv (message passing and reducing)
graph.update_all(...)
  • normalize by dst node
feat = feat * norm

Could you please explain it further?

Thanks again.

#6

For H^{(l+1)}=\tilde{D}^{-\frac{1}{2}}\tilde{A}H^{(l)}W^{(l)}, element-wise, the update rule for a node v is then

H_{v,:}^{(l+1)}=\frac{1}{\sqrt{d_v}}\sum_{u\in\mathcal{N}(v)}W^{(l)}H_{u, :}^{(l)}

Hence, you don’t need to perform the normalization for source nodes before message passing, just normalize by dst nodes once you complete graph.update_all(...).

1 Like