Answers.Body: <p>If I understand correctly, the concept is to, first, embed the given graphs using the graph isomorphism network (GIN) <a href="https://arxiv.org/abs/1810.00826" rel="nofollow noreferrer">[Xu et al.]</a> and then, for the GED, feed any two embeddings <span class="math-container">$\mathbf{x}_{\mathcal{G}_1}$</span> and <span class="math-container">$\mathbf{x}_{\mathcal{G}_2}$</span> of graphs <span class="math-container">$\mathcal{G}_1$</span> and <span class="math-container">$\mathcal{G}_2$</span> to the euclidean norm, i.e. <span class="math-container">$\text{GED}(\mathcal{G}_1, \mathcal{G}_2) = \parallel \mathbf{x}_{\mathcal{G}_1} - \mathbf{x}_{\mathcal{G}_2} \parallel_2$</span>. This architecture is then trained to predict the graph edit distance.</p>
  <p>To my understanding, the metric properties of this approach rely entirely on the expressive power of the GIN. If the GIN generates the exact same embedding for two dissimilar graphs, then <span class="math-container">$\text{GED}(\mathcal{G}_1, \mathcal{G}_2) = 0$</span> even though <span class="math-container">$\mathcal{G}_1 \neq \mathcal{G}_2$</span> which violates the properties of a metric. As GINs expressive power is upper bounded by that of the Weisfeiler Lehman test (WL-test) (cf. <a href="https://arxiv.org/abs/1810.00826" rel="nofollow noreferrer">Xu et al.</a>), you can easily find such pairs of graphs. For more on this, you can read <a href="https://towardsdatascience.com/expressive-power-of-graph-neural-networks-and-the-weisefeiler-lehman-test-b883db3c7c49" rel="nofollow noreferrer">this nice blog post</a>.</p>
  <p>At first glance, this seems to be contradicting the claim of the authors. However, as far as I understand, the authors only claim that <span class="math-container">$F$</span> preserves metric properties. Since <span class="math-container">$F$</span> is the p-norm, i.e. the GIN is excluded from the definition of <span class="math-container">$F$</span>, they are correct. The authors don't claim that the full architecture including the GIN preserves metric properties.</p>
  <p>To answer your questions:</p>
  <blockquote>
  <p>I wonder how can I prove that these properties are maintained in actual forecasts?</p>
  </blockquote>
  <p>You can only disproof that, because GIN cannot distinguish graphs that the WL-test cannot distinguish.</p>
  <blockquote>
  <p>is it enough for satisfying properties at the real prediction value to define loss function that is always satisfying properties which i want?</p>
  </blockquote>
  <p>Sadly no, this is not enough - neural networks are only function approximators, there is usually no guarantee that an NN will always satisfy the properties promoted by the loss function.</p>
  <p>The bottom line is that if you truly rely on absolutely correct measurements, then you should not use this approach. However, exact measurements take a lot of time to compute (as the authors say it's an NP-hard problem). Therefore, this method presents a tradeoff between accuracy and time complexity. If the accuracy suffices, then it can be orders of magnitude faster than explicitly computing GED.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-04-28T15:48:47.710Z
Answers.LastActivityDate: 2023-04-28T15:48:47.710Z
Answers.UserDisplayName: Chillston
Body: <p>In this paper &quot;GREED: A Neural Framework for Learning Graph Distance Functions&quot;, function F is defined to satisfy metric property and triangle inequality property.</p>
  <p>I wonder how can I prove that these properties are maintained in actual forecasts? Or does defining the F function like that make it a natural fact without having to prove it?</p>
  <p>These are the architecture in the paper. <a href="https://i.sstatic.net/w1Idp.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/w1Idp.png" alt="here" /></a></p>
  <p>I'm not sure.. If I want to make a model using deep learning, is it enough for satisfying properties at the real prediction value to define loss function that is always satisfying properties which i want?</p>
  
Tags: <deep-learning><graph-neural-networks><graph-search>
Title: GREED - preservation theoretical properties in the GED(graph edit distance) pridiction
UserDisplayName: GH HONG
ThreadText: # GREED - preservation theoretical properties in the GED(graph edit distance) pridiction
  
  (Asked by: username_0 on 2023-04-28)
  
  In this paper "GREED: A Neural Framework for Learning Graph Distance Functions", function F is defined to satisfy metric property and triangle inequality property.
  
  I wonder how can I prove that these properties are maintained in actual forecasts? Or does defining the F function like that make it a natural fact without having to prove it?
  
  These are the architecture in the paper. [![here](https://i.sstatic.net/w1Idp.png)](https://i.sstatic.net/w1Idp.png)
  
  I'm not sure.. If I want to make a model using deep learning, is it enough for satisfying properties at the real prediction value to define loss function that is always satisfying properties which i want?
  
  **Tags:** deep-learning, graph-neural-networks, graph-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-04-28. Score: 1 | Accepted answer
  
  If I understand correctly, the concept is to, first, embed the given graphs using the graph isomorphism network (GIN) [[Xu et al.]](https://arxiv.org/abs/1810.00826) and then, for the GED, feed any two embeddings $\mathbf{x}\_{\mathcal{G}\_1}$ and $\mathbf{x}\_{\mathcal{G}\_2}$ of graphs $\mathcal{G}\_1$ and $\mathcal{G}\_2$ to the euclidean norm, i.e. $\text{GED}(\mathcal{G}\_1, \mathcal{G}\_2) = \parallel \mathbf{x}\_{\mathcal{G}\_1} - \mathbf{x}\_{\mathcal{G}\_2} \parallel\_2$. This architecture is then trained to predict the graph edit distance.
  
  To my understanding, the metric properties of this approach rely entirely on the expressive power of the GIN. If the GIN generates the exact same embedding for two dissimilar graphs, then $\text{GED}(\mathcal{G}\_1, \mathcal{G}\_2) = 0$ even though $\mathcal{G}\_1 \neq \mathcal{G}\_2$ which violates the properties of a metric. As GINs expressive power is upper bounded by that of the Weisfeiler Lehman test (WL-test) (cf. [Xu et al.](https://arxiv.org/abs/1810.00826)), you can easily find such pairs of graphs. For more on this, you can read [this nice blog post](https://towardsdatascience.com/expressive-power-of-graph-neural-networks-and-the-weisefeiler-lehman-test-b883db3c7c49).
  
  At first glance, this seems to be contradicting the claim of the authors. However, as far as I understand, the authors only claim that $F$ preserves metric properties. Since $F$ is the p-norm, i.e. the GIN is excluded from the definition of $F$, they are correct. The authors don't claim that the full architecture including the GIN preserves metric properties.
  
  To answer your questions:
  
  > I wonder how can I prove that these properties are maintained in actual forecasts?
  
  You can only disproof that, because GIN cannot distinguish graphs that the WL-test cannot distinguish.
  
  > is it enough for satisfying properties at the real prediction value to define loss function that is always satisfying properties which i want?
  
  Sadly no, this is not enough - neural networks are only function approximators, there is usually no guarantee that an NN will always satisfy the properties promoted by the loss function.
  
  The bottom line is that if you truly rely on absolutely correct measurements, then you should not use this approach. However, exact measurements take a lot of time to compute (as the authors say it's an NP-hard problem). Therefore, this method presents a tradeoff between accuracy and time complexity. If the accuracy suffices, then it can be orders of magnitude faster than explicitly computing GED.
  
  
  ---
  
  