5 ms·

If you use a standard distance metric for your embedding space, won't the triangle inequality still imply a slightly weaker version of these chains? I.e. if A-B

If you use a standard distance metric for your embedding space, won't the triangle inequality still imply a slightly weaker version of these chains? I.e. if A-B and B-C are both smaller than epsilon, then A-C is smaller than 2*epsilon?

zwaps 5y ago
Yes The embedding needs to embed a social graph with similarity weights and predict ties. Of course, such partly cyclical graphs can not be guaranteed to embed in a low dimensional (aka far away from N) Euclidian or even Hyperbolic space. Which means, among other things, that throwing any old Pytorch NN at the problem will not work, similar to how you can’t just Word2Vec to GPT performance since the latter employs many parallel Euclidian embeddings (or, in other words, any selection or aggregation of layer embedding is contextual). Not that you can’t do it on Graphs, it’s just that understanding the issues is very helpful. For example, understanding that Euclidian embeddings imply a triangle inequality while social graphs of similarity do not, is a crucial thing to know before throwing stuff at pytorch.
- phreeza 5y ago
  I like the analogy to multi-head attention. Is there work on something like it for collaborative filtering embeddings, eg splitting up the vector into multiple subvectors and calculating distances separately?
  - zwaps 5y ago
    Not sure about CF but in terms of representation learning there are, of course, transformer approaches to embedding graphs ( the article essentially talks about the predictive power of closed triads in a graph) So, a good starting point might be SDNE type graph embeddings with a transformer architecture, since these are already encoder/decoder setups. There’s a ton of ways to get node similarity in a graph, but it turns out that all of them have a substantive theory basis (walks versus neighborhoods, higher order structure vs proximity etc) and none of them are really just “NN, embedding and done“ Perhaps also because it is really simple to see ex ante that a flat Euclidian embedding can not work.
Straw 5y ago
That's right, but we don't need to use the Euclidean distance directly, and in fact most often we don't. For example, we usually use dot product, and predict success between two users as sigmoid(A.B), then we can have A.B > 0 and B.C > 0 but A.C < 0, so there's no problem. We can get the same with Euclidean metric too, by (soft) thresholding- anyway we have to map from our distance to a prediction of the interaction somehow.

zwaps 5y ago

Yes The embedding needs to embed a social graph with similarity weights and predict ties. Of course, such partly cyclical graphs can not be guaranteed to embed in a low dimensional (aka far away from N) Euclidian or even Hyperbolic space. Which means, among other things, that throwing any old Pytorch NN at the problem will not work, similar to how you can’t just Word2Vec to GPT performance since the latter employs many parallel Euclidian embeddings (or, in other words, any selection or aggregation of layer embedding is contextual). Not that you can’t do it on Graphs, it’s just that understanding the issues is very helpful. For example, understanding that Euclidian embeddings imply a triangle inequality while social graphs of similarity do not, is a crucial thing to know before throwing stuff at pytorch.

phreeza 5y ago
I like the analogy to multi-head attention. Is there work on something like it for collaborative filtering embeddings, eg splitting up the vector into multiple subvectors and calculating distances separately?
- zwaps 5y ago
  Not sure about CF but in terms of representation learning there are, of course, transformer approaches to embedding graphs ( the article essentially talks about the predictive power of closed triads in a graph) So, a good starting point might be SDNE type graph embeddings with a transformer architecture, since these are already encoder/decoder setups. There’s a ton of ways to get node similarity in a graph, but it turns out that all of them have a substantive theory basis (walks versus neighborhoods, higher order structure vs proximity etc) and none of them are really just “NN, embedding and done“ Perhaps also because it is really simple to see ex ante that a flat Euclidian embedding can not work.

Straw 5y ago

That's right, but we don't need to use the Euclidean distance directly, and in fact most often we don't. For example, we usually use dot product, and predict success between two users as sigmoid(A.B), then we can have A.B > 0 and B.C > 0 but A.C < 0, so there's no problem. We can get the same with Euclidean metric too, by (soft) thresholding- anyway we have to map from our distance to a prediction of the interaction somehow.