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

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.

• Possibly relevant: Hierarchical Graph Representation Learning with Differentiable Pooling (2019) May 16, 2020 at 9:04
• This post is still a bit unclear to me. Is $H$ a distance matrix? I don't see the relationship between $H$ and $D^{-1}AH$ that you describe in the second point, and I don't actually understand your Problem part, because $\mathbb{p}$ does not contain $D^{-1}AH$. Probably I don't understand that part because I didn't read that linked paper and it's been a while since I had to deal with geometric deep learning. Also, what is $k$? Is it an iteration number?
– nbro
May 16, 2020 at 17:11
• @nbro "I don't see the relationship between H and D−1AH that you describe in the second point" that is exactly my problem - I don't see this relationship either, but it's how the authors describe the formula. It just looks like simply multiplying this $H$ by the graph's random walk Laplacian, but they have described it differently and I don't understand how their description fits. And $k$ is the layer index (this process happens repeatedly at increasingly 'pooled' representations of the graph). May 16, 2020 at 17:23
• @brazofuerte you may want to check out LEConv GNN formulation introduced in this AAAI 2020 paper: arxiv.org/abs/1911.07979 . They sample clusters by finding the importance of a cluster wrt its neighboring clusters via a learnable difference function using LEConv. May 21, 2020 at 11:56

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.