# Optimal Dimension of Graph(Vertex) Embedding [closed]

Let's define a embedding of a graph structure G = (V,E) where $$\mid V\mid=v, \mid E \mid=e$$

Now define an embedding $$f: V \to R^d$$ where $$d\in \Bbb N$$, an optimal dimension of embedding which contains every edge information of $$G$$.

(G is a directed graph and there exist no weight, thus it's not a network.)

I'd like to find an infimum formula of $$d$$ represented with $$v$$ and $$e$$.

[Backgroud of this problem]

I am trying to construct a neural network which can discern whether the given explanation of word is about the word "be" or the word "exist".

For example "having a real existence" is "exist". To do this, first I need to find the most smallest dimension of each words' corresponding embedding of vertex for training of my network.

## 1 Answer

I think that finding the absolute dimension of expressivity is a difficult problem. Here are some important facts to consider when you come with a word embedding size.

1. Make sure you leave enough dimensions for expressivity. You want to make sure that there is at least enough dimensions to express the complexity of the structure you are looking to encode
2. That the number of dimensions is not too large so that you suffer some difficulties in computation.

To conclude, finding the infimum can be done post-hoc, in the sense that you can evaluate the performance on the function and see which value of $d$ does not significantly decrease the performance and choose it this way. However, at a post-hoc level, the only way I can see of doing this is by evaluating the embedding space beforehand, I have not read too much literature about this.

1. https://arxiv.org/pdf/1711.00331.pdf - Semantic Structure and Interpretability of Word Embeddings

There is also a lot of work done to evaluate the embedding schemes that we have chosen. In the recent NAACL conference there has been work that has been done in this domain particularly.