6
$\begingroup$

I wrote an algorithm for generating node embeddings based on the graph's topology. Most of the explanation is done in the readme file and the examples.

The question is: Am I reinventing the wheel? Does this approach have any practical advantages over existing solutions for embeddings generation?

Yes, I'm aware there are many algorithms for this based on random walks, but this one is pure deterministic linear algebra and it is quite simple, from my perspective.

In short, the algorithm is heavily inspired by PageRank. Every node is described by its proximity vector which contains the node's closeness number to every other node or some selected subset of the nodes. The "closeness" is not just the simple shortest distance.

Here's brief explanation from the repo's readme for directed/undirected unweighted graph (the idea generalizes to weighted graphs pretty intuitively):

  1. Every node is assigned a vector. For node i the vector's j-th element is a number representing its closeness to node j (you can think of it as signal strength).
  2. The closeness of the node i to the node j (the "central" node the signal flows from) is defined as a sum of the signal strengths of the neighboring nodes multiplied by the damping factor parameter. (The dumping factor works like a kind of distance penalty)
  3. Signal a node "emits" to other connected nodes equal to the given signal's strength in the node itself divided by the number of edges it is able to emit to.
  4. Initially, the node j is assigned a closeness (to itself) equal to 1.

The whole thing is computed by solving sparse linear systems.

"Signal" strengths from node 4 to other nodes. Note that the signal here travel in direction opposite to edge direction (like "follow" relation on Instagram)

"Signal" strengths from node 4 to other nodes. Note that the signal here travel in direction opposite to edge direction (like "follow" relation on Instagram)

$\endgroup$
  • $\begingroup$ Hi @monomonedula, have a look at multidimensional scaling (MDS). en.wikipedia.org/wiki/Multidimensional_scaling It sounds like it has a similar set up (it works on a distance/similarity matrix), and finds the embedding of those points such that the embedded distances are as close as possible to those specified distances. Your set up is sparse though - maybe a "sparse MDS" exists? $\endgroup$ – bogovicj May 26 at 14:50
  • $\begingroup$ You can check https://github.com/graknlabs/kglib if its similar to what you are trying to achieve. $\endgroup$ – Syenix Aug 6 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.