Add algorithm for RandomWalk

[czgdp1807]

Description of the problem

Once we are done adding basic framework for Graphs, we can start thinking of adding RandomWalk algorithm.
We first need to decide the feasibility of implementation of the above algorithm.

Example of the problem

References/Other comments

[1] Directly go to #65 (comment)
[2] https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf

[Saptashrungi]

Is this issue up for implementation? What are basic requirements in case of graphs?

[czgdp1807]

One has to read this paper, https://arxiv.org/pdf/1403.6652.pdf and see how the current Graph API in master can be used or what modifications are needed in it to implement this algorithm. This issue will require a series of PRs with different components added in each to get the algorithm implemented successfully.

[Saptashrungi]

Okay, I will give it try.

[Saptashrungi]

I would like to work on this issue as it seems interesting to me. I read the paper as well as went through the algorithm. I understood some of it and at some places I am stuck. For eg:

Φ∈R|V|×d: Initialization: Sample Φ from U|V|×d

What is U here?
d is embedding size.
The sample Φ is a vector space I assume.

I will soon make a PR with a rough code. It will also contain code for random_walk. This function does not however implement Random Walk with Restart (RWR), as the paper you provided said that restarts are not necessary for deep walk. I would like to discuss whether or not to include restarts in random walk function, if necessary we can modify the code accordingly.
I haven't searched about SkipGram. I will do it next.

[czgdp1807]

I will soon make a PR with a rough code.

PR will be too early, without having discussions on design. We don't even know whether the APIs for graphs will be enough for implementing this. We need to pick the simplest algorithm in the paper(if there are multiple) and discuss on it first.

[czgdp1807]

In fact, they have used the following as inputs to the algorithm,

1. w, window size
2. d, embedding size
3. g, walks per vertex
4. t, walk length

What all do they mean and how can we represent them in pydatastructs?

[Saptashrungi]

I am still reading about them. For now only Random Walk can be implemented using AdjacencyList.

…

On Sun, 22 Mar, 2020, 7:17 PM Gagandeep Singh, ***@***.***> wrote: In fact, they have used the following as inputs to the algorithm, 1. *w*, window size 2. *d*, embedding size 3. *g*, walks per vertex 4. *t*, walk length What all do they mean and how can we represent them in pydatastructs? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#65 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ALEKQUJ6MGBTWLPPL7COPTDRIYJHLANCNFSM4J7KOKLQ> .

[czgdp1807]

I am still reading about them

I think first that part should be clarified as they are going to be at the entry points of the deep walk algorithm.

[Saptashrungi]

Window size is the basically the size of the surrounding area of the node which we are considering for node embedding in a graph. We can set the window size according to our convenience.
For example if its value is x, then we can make an edge list where we represent the node and the neighbors associated with node under consideration in the given window size.

[czgdp1807]

It looks like all the variables in #65 (comment) are integers, so no extra framework is needed to support these values?
Can you confirm that?

[Saptashrungi]

Yes. The algorithm can be implemented with existing framework.
How do I proceed? I got the concept. Deepwalk is basically Random walk+ Skipgram.

[czgdp1807]

We first need to decide the feasibility of implementation of the above algorithm.

The problems which we will face,

1. DeepWalk relates to graphs but not in a way which should keep the algorithm in the scope of this project.
2. SkipGram is an optimisation algorithm which again doesn't suit the repository.
3. RandomWalk can be implemented only if there are enough use cases for the following output i.e., the transcript of a random walk.

While the transcript (the list of vertices in the order they are
visited) of a particular random walk is sometimes of interest

The issue title can be narrowed down to RandomWalk but still the question of feasibility remains to be answered before moving towards the first step i.e., API design.

References

.. [1] https://www.cs.yale.edu/homes/spielman/561/lect10-18.pdf