Link prediction on network embeddings
The short answer is:
You are correct, in order to compute node embeddings you only need the "true" train edges. These edges span a training graph which is the input we give NE methods to learn the node embeddings. Non-edges are only used in the binary classification problem.

The longer answer is:
The most effective way to compute link predictions from embeddings is via binary classification. The node embeddings first need to be transformed into edge embeddings (e.g. averaging the embeddings of i and j to get the embedding of e=(i,j)) and then solve a binary classification problem. The binary classifier (usually Logistic regression) will take the edge embeddings as examples and try to learn a mapping to their corresponding "label" where these labels are 1 for the "true" edges and 0 for the non-edges. Therefore, in addition to the edge embeddings of "true" graph edges, we need to compute the edge embeddings of a set of non-edges in the graphs (those with label 0). This is what we usually refer to when we talk about negative sampling for LP.

I believe the confusion here comes from the way some popular NE algorithms compute the embeddings. For instance, methods base on matrix factorization directly take the train graph you give as input, compute the adjacency matrix, factorize it and return the node embeddings. Other methods e.g. Deepwalk, Node2vec or LINE have a special way of learning embeddings (Skip-gram from work embedding literature) and require "negative sampling" in the embedding learning process itself. These methods will select, from that train graph you give them, a set of non-edges or paths of non-connected edges to learn which node vectors should be put close together and which should be far. The NE methods will select these samples of non-edges themselves and in different ways, so the user generally doesn't have any control over it.

I hope this clarifies your question.