Answers.Body: <p>Here, <span class="math-container">$H$</span> is a <span class="math-container">$n * d$</span> matrix where <span class="math-container">$n$</span> is the number of total nodes in the graph and <span class="math-container">$d$</span> is the dimension of embedding of each node. </p>
  
  <p>Using the notation in the question, the basic GNN formulation without self loop is: <span class="math-container">$\text{D}^{-1}\text{A}\text{H}$</span>. If you study this equation closer then you will find that the <span class="math-container">$i^{th}$</span> row of <span class="math-container">$\text{A}\text{H}$</span> generates the <span class="math-container">$i^{th}$</span> node's representation by summing the node representation of its neighboring nodes. Multiplying it with <span class="math-container">$\text{D}^{-1}$</span> makes the aggregated representation normalized with respect to the degree of a node (number of neighbors). </p>
  
  <p>By defining a metric called information score:
  <span class="math-container">$$||\text{H} - (\text{D}^{-1}\text{A}\text{H})||$$</span>
  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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-20T21:15:41.697Z
Answers.LastActivityDate: 2020-05-20T21:33:16.993Z
Answers.LastEditDate: 2020-05-20T21:33:16.993Z
Answers.UserDisplayName: user1825567
Body: <p>The paper <a href="https://arxiv.org/pdf/1911.05954.pdf" rel="nofollow noreferrer">Hierarchical Graph Pooling with Structure Learning</a> (2019) introduces a distance measure between:</p>
  <ol>
  <li>a graph's node-representation matrix <span class="math-container">$\text{H}$</span>, and</li>
  <li>an approximation of this constructed from each node's neighbours' information <span class="math-container">$\text{D}^{-1}\text{A}\text{H}$</span>:</li>
  </ol>
  <blockquote>
  <p>Here, we formally define the node information score as the Manhattan distance between the node representation itself and the one constructed from its neighbors:</p>
  <p><span class="math-container">$$\mathbb{p} = \gamma(\mathcal{G}_i) = ||(\text{I}^{k}_{i} - (\text{D}^{k}_{i})^{-1}\text{A}^{k}_{i})\text{H}^{k}_{i}||  $$</span></p>
  </blockquote>
  <p><sup>(where <span class="math-container">$\text{A}$</span> and <span class="math-container">$\text{D}$</span> are the Adjacency and Diagonal matrices of the graph, respectively)</sup></p>
  <p>Expanding the product on the RHS we get (ignoring index notation for simplicity):</p>
  <p><span class="math-container">$$||\text{H} - (\text{D}^{-1}\text{A}\text{H})||$$</span></p>
  <p><strong>Problem:</strong> I don't see how <span class="math-container">$\text{D}^{-1}\text{A}\text{H}$</span> is a &quot;node representation... constructed from its neighbors&quot;.</p>
  <p><span class="math-container">$\text{I} - \text{D}^{-1}\text{A}$</span> is clearly equivalent to the <a href="https://en.wikipedia.org/wiki/Laplacian_matrix#Random_walk_normalized_Laplacian" rel="nofollow noreferrer">Random Walk Laplacian</a>, but it's not immediately obvious to me how multiplying this by <span class="math-container">$\text{H}$</span> provides per-node information on how well one can reconstruct a node from its neighbours.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-16T09:04:13.227Z
Comments.Text: Possibly relevant: [Hierarchical Graph Representation Learning with Differentiable Pooling](https://arxiv.org/abs/1806.08804) (2019)
Comments.UserDisplayName: brazofuerte
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-16T17:11:57.790Z
Comments.Text: 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?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-16T17:23:02.600Z
Comments.Text: @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).
Comments.UserDisplayName: brazofuerte
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-21T11:56:18.860Z
Comments.Text: @brazofuerte you may want to check out LEConv GNN formulation introduced in this AAAI 2020 paper: https://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.
Comments.UserDisplayName: user1825567
Tags: <papers><geometric-deep-learning><graph-neural-networks><spectral-analysis>
Title: Understanding the node information score in the paper "Hierarchical Graph Pooling with Structure Learning"
UserDisplayName: brazofuerte
ThreadText: # Understanding the node information score in the paper "Hierarchical Graph Pooling with Structure Learning"
  
  (Asked by: username_0 on 2020-05-16)
  
  The paper [Hierarchical Graph Pooling with Structure Learning](https://arxiv.org/pdf/1911.05954.pdf) (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](https://en.wikipedia.org/wiki/Laplacian_matrix#Random_walk_normalized_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.
  
  **Tags:** papers, geometric-deep-learning, graph-neural-networks, spectral-analysis
  > **Comments:**
  > **username_0**: Possibly relevant: [Hierarchical Graph Representation Learning with Differentiable Pooling](https://arxiv.org/abs/1806.08804) (2019)  
  > **username_1**: 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?  
  > **username_0**: @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).  
  > **username_2**: @brazofuerte you may want to check out LEConv GNN formulation introduced in this AAAI 2020 paper: https://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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-05-20. Score: 2 | Accepted answer
  
  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.
  
  
  ---
  
  