# GREED - preservation theoretical properties in the GED(graph edit distance) pridiction

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.

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?

If I understand correctly, the concept is to, first, embed the given graphs using the graph isomorphism network (GIN) [Xu et al.] 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.), you can easily find such pairs of graphs. For more on this, you can read this nice blog post.

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.