Understanding the node information score in the paper "Hierarchical Graph Pooling with Structure Learning"

Question

The paper Hierarchical Graph Pooling with Structure Learning (2019) introduces a distance measure between:

1. a graph's node-representation matrix $\text{H}$, and
2. an approximation of this constructed from each node's neighbours' information $\text{D}^{-1}\text{A}\text{H}$:

Here, we formally define the node information score as the Manhattan distance between the node representation itself and the one constructed from its neighbors:

$$\mathbb{p} = \gamma(\mathcal{G}_i) = ||(\text{I}^{k}_{i} - (\text{D}^{k}_{i})^{-1}\text{A}^{k}_{i})\text{H}^{k}_{i}|| $$

^{(where $\text{A}$ and $\text{D}$ are the Adjacency and Diagonal matrices of the graph, respectively)}

Expanding the product on the RHS we get (ignoring index notation for simplicity):

$$||\text{H} - (\text{D}^{-1}\text{A}\text{H})||$$

Problem: I don't see how $\text{D}^{-1}\text{A}\text{H}$ is a "node representation... constructed from its neighbors".

$\text{I} - \text{D}^{-1}\text{A}$ is clearly equivalent to the Random Walk Laplacian, but it's not immediately obvious to me how multiplying this by $\text{H}$ provides per-node information on how well one can reconstruct a node from its neighbours.

Answer 1

Here, $H$ is a $n * d$ matrix where $n$ is the number of total nodes in the graph and $d$ is the dimension of embedding of each node.

Using the notation in the question, the basic GNN formulation without self loop is: $\text{D}^{-1}\text{A}\text{H}$. If you study this equation closer then you will find that the $i^{th}$ row of $\text{A}\text{H}$ generates the $i^{th}$ node's representation by summing the node representation of its neighboring nodes. Multiplying it with $\text{D}^{-1}$ makes the aggregated representation normalized with respect to the degree of a node (number of neighbors).

By defining a metric called information score: $$||\text{H} - (\text{D}^{-1}\text{A}\text{H})||$$ we will be getting low values for nodes that are well represented by their local neighborhood nodes and high values for nodes that are having a hard time being represented/summarized by its neighboring nodes. To approximate the graph information, the authors choose to preserve the nodes that can not be well represented by their neighbors, i.e., the nodes with relatively larger node information score will be preserved in the construction of the pooled graph, because the authors believe it can provide more information.