Answers.Body: <p>The proof of the first statement can be found in these <a href="https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture7.pdf" rel="nofollow noreferrer">Lecture Notes</a>.</p>
  <p>Have a look of the Proof of the <em>Claim 1</em>.</p>
  <p>Concerning the <em>renormalization trick</em> I do not see easy way to justify this statement. <a href="https://arxiv.org/pdf/1902.07153.pdf" rel="nofollow noreferrer">The paper</a> claims:</p>
  <blockquote>
  <p>i.e. adding self-loops to the graph, improves accuracy, and we
  demonstrate that this method effectively shrinks the graph spectral
  domain, resulting in a low-pass-type filter when applied to SGC.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-31T16:44:52.747Z
Answers.LastActivityDate: 2021-08-31T16:44:52.747Z
Answers.UserDisplayName: spiridon_the_sun_rotator
Body: <p>In <a href="https://arxiv.org/pdf/1609.02907.pdf" rel="nofollow noreferrer">Semi-supervised classification with Graph Convolutional Networks</a>, I am unable to understand a few things.</p>
  <p>Given an undirected graph having</p>
  <ul>
  <li>adjacency matrix <span class="math-container">$A$</span>,</li>
  <li>degree matrix <span class="math-container">$D_{ii} = \sum_j A_{ij}$</span>,</li>
  <li>normalized graph laplacian <span class="math-container">$L = I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}} = U \Lambda U^T$</span>, where <span class="math-container">$\lambda_{max} \approx 2$</span> (see page 3, 2nd paragraph, not sure which matrix they are talking about)</li>
  </ul>
  <p>Then, <span class="math-container">$I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$</span> has eigenvalues in the range [0, 2]. How?</p>
  
Tags: <papers><convolution><geometric-deep-learning><graph-neural-networks><linear-algebra>
Title: Why does $I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ have eigenvalues in the range [0, 2]?
UserDisplayName: willtryagain
ThreadText: # Why does $I_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ have eigenvalues in the range [0, 2]?
  
  (Asked by: username_0 on 2021-08-31)
  
  In [Semi-supervised classification with Graph Convolutional Networks](https://arxiv.org/pdf/1609.02907.pdf), I am unable to understand a few things.
  
  Given an undirected graph having
  
  * adjacency matrix $A$,
  * degree matrix $D\_{ii} = \sum\_j A\_{ij}$,
  * normalized graph laplacian $L = I\_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}} = U \Lambda U^T$, where $\lambda\_{max} \approx 2$ (see page 3, 2nd paragraph, not sure which matrix they are talking about)
  
  Then, $I\_N + D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ has eigenvalues in the range [0, 2]. How?
  
  **Tags:** papers, convolution, geometric-deep-learning, graph-neural-networks, linear-algebra
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-08-31. Score: 0 | Accepted answer
  
  The proof of the first statement can be found in these [Lecture Notes](https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture7.pdf).
  
  Have a look of the Proof of the *Claim 1*.
  
  Concerning the *renormalization trick* I do not see easy way to justify this statement. [The paper](https://arxiv.org/pdf/1902.07153.pdf) claims:
  
  > i.e. adding self-loops to the graph, improves accuracy, and we
  > demonstrate that this method effectively shrinks the graph spectral
  > domain, resulting in a low-pass-type filter when applied to SGC.
  
  
  ---
  
  