This is an automated email from the ASF dual-hosted git repository.
mboehm7 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemds.git
The following commit(s) were added to refs/heads/master by this push:
new 57d5ec9 [SYSTEMDS-3075] DeepWalk builtin function (graph embeddings)
57d5ec9 is described below
commit 57d5ec967803f75082ea94099322465b38ecd670
Author: max <[email protected]>
AuthorDate: Thu Jul 29 01:04:36 2021 +0200
[SYSTEMDS-3075] DeepWalk builtin function (graph embeddings)
This commit includes an implementation of DeepWalk based on the paper
(https://arxiv.org/pdf/1403.6652.pdf).
AMLS project SS2021.
Closes #1353.
Co-authored-by: Julian Göschl <[email protected]>
---
scripts/builtin/deepWalk.dml | 186 +++
.../java/org/apache/sysds/common/Builtins.java | 1 +
.../functions/builtin/BuiltinDeepWalkTest.java | 75 +
src/test/resources/datasets/caveman_4_20.ijv | 1520 ++++++++++++++++++++
src/test/resources/datasets/caveman_4_20.ijv.mtd | 7 +
src/test/scripts/functions/builtin/deepWalk.dml | 25 +
6 files changed, 1814 insertions(+)
diff --git a/scripts/builtin/deepWalk.dml b/scripts/builtin/deepWalk.dml
new file mode 100644
index 0000000..338ddaa
--- /dev/null
+++ b/scripts/builtin/deepWalk.dml
@@ -0,0 +1,186 @@
+#-------------------------------------------------------------
+#
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+#
+#-------------------------------------------------------------
+
+# This script performs DeepWalk on a given graph
(https://arxiv.org/pdf/1403.6652.pdf)
+# INPUT PARAMETERS:
+#
---------------------------------------------------------------------------------------------
+# NAME TYPE DEFAULT MEANING
+#
---------------------------------------------------------------------------------------------
+# Graph Matrix --- adjacency matrix of a graph (n x n)
+# w Integer --- window size
+# d Integer --- embedding size
+# gamma Integer --- walks per vertex
+# t Integer --- walk length
+# alpha Double 0.025 learning rate
+# beta Double 0.9 factor for decreasing learning rate
+#
---------------------------------------------------------------------------------------------
+# OUTPUT PARAMETERS:
+#
---------------------------------------------------------------------------------------------
+# NAME TYPE DEFAULT MEANING
+#
---------------------------------------------------------------------------------------------
+# Phi Matrix --- matrix of vertex/word representation (n x
d)
+
+source("scripts/staging/entity-resolution/primitives/postprocessing.dml") as
post;
+
+m_deepWalk = function(Matrix[Double] Graph, Integer w, Integer d,
+ Integer gamma, Integer t, Double alpha=0.025, Double beta=0.9)
+ return(Matrix[Double] Phi)
+{
+ word_count = nrow(Graph)
+ tree_depth = ceil(log(word_count, 2))
+
+ # build binary tree from vocabulary
+ # TODO: currently we make a full binary tree with a depth depending on the
word count e.g.:
+ # TODO: for a word count of 5, we create a binary tree with 8 leaves and 7
nodes
+ T = createBinaryTreeMatrix(word_count)
+
+ # initialize the the node vectors and the representation matrix Phi with
random values [0, 1]
+ # TODO: we initialize full binary tree -> not necessary if we have less
leaves
+ Theta = rand(rows=2^tree_depth-1, cols=d)
+ Phi = rand(rows=word_count, cols=d)
+
+ for (i in 1:gamma) {
+ vocab_shuffled = sample(word_count, word_count, FALSE)
+ for (node_idx in 1:length(vocab_shuffled)) {
+ random_walk = randomWalk(Graph, as.scalar(vocab_shuffled[node_idx]), t)
+ [Phi, Theta] = skipGram(Phi, Theta, T, random_walk, w, alpha)
+ }
+ # decreasing learning rate
+ alpha = alpha * beta
+ }
+}
+
+# binary tree as adjacency matrix
+createBinaryTreeMatrix = function(Integer word_count)
+ return(Matrix[Double] Tree)
+{
+ rix = matrix(seq(1,word_count-1) %*% matrix(1,1,2), 2*(word_count-1), 1)
+ cix = 1+seq(1,2*(word_count-1));
+ Tree = table(rix, cix); # place 1s into output
+}
+
+randomWalk = function(Matrix[Double] Graph, Integer start_vertex, Integer
walk_length)
+ return(Matrix[Double] random_walk)
+{
+ random_walk = matrix(0, rows=walk_length+1, cols=1)
+ random_walk[1] = start_vertex
+
+ current_vertex = start_vertex
+ for (i in 1:walk_length) {
+ neighbors_untable = post::untable(Graph[current_vertex, ])
+ neighbors = neighbors_untable[, 2]
+ index = as.scalar(sample(nrow(neighbors), 1))
+ current_vertex = as.scalar(neighbors[index])
+ random_walk[i+1] = current_vertex
+ }
+}
+
+skipGram = function(Matrix[double] Phi, Matrix[double] Theta,
+ Matrix[double] Tree, Matrix[double] walk, Integer window_size, Double alpha)
+ return(Matrix[double] Phi_new, Matrix[double] Theta_new)
+{
+ Phi_new = Phi
+ Theta_new = Theta
+ tree_depth = ceil(log(nrow(Phi), 2))
+
+ # TODO: check if parallelizable for different datasets; works for current
test -> sparsity, updates
+ parfor (w_i in 1:nrow(walk), check=0) {
+ # calculate furthest left/right node in the window
+ min_val = max(1, w_i-window_size)
+ max_val = min(nrow(walk), w_i+window_size)
+
+ if (w_i != 1) {
+ left_neighbors = walk[min_val:(w_i-1)]
+ for (u_k in 1:nrow(left_neighbors)) {
+ [Phi_new, Theta_new] = update(Phi_new, Theta_new,
+ Tree, tree_depth, as.scalar(left_neighbors[u_k]),
as.scalar(walk[w_i]), alpha)
+ }
+ }
+ if (w_i != nrow(walk)) {
+ right_neighbors = walk[(w_i+1):max_val]
+ for (u_k in 1:nrow(right_neighbors)) {
+ [Phi_new, Theta_new] = update(Phi_new, Theta_new,
+ Tree, tree_depth, as.scalar(right_neighbors[u_k]),
as.scalar(walk[w_i]), alpha)
+ }
+ }
+ }
+}
+
+update = function(Matrix[double] Phi, Matrix[double] Theta,
+ Matrix[double] Tree, Integer tree_depth, Integer u, Integer v, Double alpha)
+ return (Matrix[double] Phi_new, Matrix[double] Theta_new)
+{
+ Phi_new = Phi
+ Theta_new = Theta
+
+ u_binary = toBinaryArray(u, tree_depth)
+ path_to_u = getNodeIds(Tree, u_binary)
+
+ gradients = computeGradients(u, v, Theta, path_to_u, Phi, tree_depth)
+
+ # compute negative gradient for Theta update
+ neg_gradient = gradients * Phi[v]
+ for (i in 1:nrow(gradients))
+ Theta_new[as.scalar(path_to_u[i])] = Theta_new[as.scalar(path_to_u[i])] +
alpha * neg_gradient[i]
+
+ # compute negative gradient for Phi update
+ P = table(seq(1,tree_depth), path_to_u[1:tree_depth], tree_depth,
nrow(Theta));
+ target_theta = P %*% Theta;
+ neg_gradient = t(gradients) %*% target_theta
+ Phi_new[v] = Phi_new[v] + alpha * neg_gradient
+}
+
+computeGradients = function(Integer u, Integer v, Matrix[double] Theta,
+ Matrix[double] path, Matrix[double] Phi, Integer tree_depth)
+ return(Matrix[Double] gradients)
+{
+ u_binary = toBinaryArray(u, tree_depth)
+ P = table(seq(1,tree_depth), path, tree_depth, nrow(Theta));
+ u_dot_v = P %*% Theta %*% t(Phi[v]);
+ gradients = u_binary - sigmoid(u_dot_v);
+}
+
+toBinaryArray = function(Integer node_id, Integer tree_depth)
+ return(Matrix[double] binary_array)
+{
+ binary_array = matrix(0, rows=tree_depth, cols=1)
+ for (i in 1:tree_depth) {
+ binary_array[i] = node_id %% 2
+ node_id = node_id %/% 2
+ }
+}
+
+# based on a binary sequence get the correct path in the tree
+# return a list of node ids on the path to the leaf without the leaf node
itself
+getNodeIds = function(Matrix[double] Tree, Matrix[double] binary_array)
+ return(Matrix[double] node_id_array)
+{
+ seq_len = nrow(binary_array)
+ node_id_array = matrix(0, rows=seq_len, cols=1)
+ cur_node_id = 1
+ node_id_array[1] = cur_node_id
+ for (i in 1:(seq_len-1)) {
+ neighbors_untable = post::untable(Tree[cur_node_id, ])
+ neighbors = neighbors_untable[, 2]
+ node_id_array[i+1] = as.scalar(neighbors[1 + as.scalar(binary_array[i])])
+ cur_node_id = as.scalar(node_id_array[i+1])
+ }
+}
diff --git a/src/main/java/org/apache/sysds/common/Builtins.java
b/src/main/java/org/apache/sysds/common/Builtins.java
index 4c07d19..e252b20 100644
--- a/src/main/java/org/apache/sysds/common/Builtins.java
+++ b/src/main/java/org/apache/sysds/common/Builtins.java
@@ -105,6 +105,7 @@ public enum Builtins {
DBSCAN("dbscan", true),
DECISIONTREE("decisionTree", true),
DECOMPRESS("decompress", false),
+ DEEPWALK("deepWalk", true),
DETECTSCHEMA("detectSchema", false),
DENIALCONSTRAINTS("denialConstraints", true),
DIAG("diag", false),
diff --git
a/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinDeepWalkTest.java
b/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinDeepWalkTest.java
new file mode 100644
index 0000000..2a7cadc
--- /dev/null
+++
b/src/test/java/org/apache/sysds/test/functions/builtin/BuiltinDeepWalkTest.java
@@ -0,0 +1,75 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.functions.builtin;
+
+import org.apache.sysds.common.Types.ExecMode;
+import org.apache.sysds.common.Types.ExecType;
+import org.apache.sysds.test.AutomatedTestBase;
+import org.apache.sysds.test.TestConfiguration;
+import org.junit.Test;
+
+import java.io.IOException;
+
+public class BuiltinDeepWalkTest extends AutomatedTestBase {
+
+ private final static String TEST_NAME = "deepWalk";
+ private final static String TEST_DIR = "functions/builtin/";
+ private static final String TEST_CLASS_DIR = TEST_DIR +
BuiltinDeepWalkTest.class.getSimpleName() + "/";
+ private final static String RESOURCE_DIRECTORY =
"./src/test/resources/datasets/";
+
+ @Override
+ public void setUp() {
+ addTestConfiguration(TEST_NAME, new
TestConfiguration(TEST_CLASS_DIR, TEST_NAME, new String[]{"B"}));
+ }
+
+ @Test
+ public void testRunDeepWalkCP() throws IOException {
+ runDeepWalk(5, 2, 5, 10, -1, -1, ExecType.CP);
+ }
+
+ private void runDeepWalk(int window_size, int embedding_size, int
walks_per_vertex, int walk_length,
+ double alpha, double beta, ExecType execType) throws
IOException
+ {
+ ExecMode platformOld = setExecMode(execType);
+
+ try {
+ loadTestConfiguration(getTestConfiguration(TEST_NAME));
+ String HOME = SCRIPT_DIR + TEST_DIR;
+ fullDMLScriptName = HOME + TEST_NAME + ".dml";
+
+ programArgs = new String[]{
+ "-nvargs", "GRAPH=" + RESOURCE_DIRECTORY +
"caveman_4_20.ijv",
+ "WINDOW_SIZE=" + window_size,
+ "EMBEDDING_SIZE=" + embedding_size,
+ "WALKS_PER_VERTEX=" + walks_per_vertex,
+ "WALK_LENGTH=" + walk_length,
+ "OUT_FILE=" + output("B")
+ };
+
+ runTest(true, false, null, -1);
+
+ // TODO for verification plot the output "B" e.g.:
+ // in python -> clearly separable clusters for this test
+ }
+ finally {
+ rtplatform = platformOld;
+ }
+ }
+}
diff --git a/src/test/resources/datasets/caveman_4_20.ijv
b/src/test/resources/datasets/caveman_4_20.ijv
new file mode 100644
index 0000000..1912568
--- /dev/null
+++ b/src/test/resources/datasets/caveman_4_20.ijv
@@ -0,0 +1,1520 @@
+1 3 1
+1 4 1
+1 5 1
+1 6 1
+1 7 1
+1 8 1
+1 9 1
+1 10 1
+1 11 1
+1 12 1
+1 13 1
+1 14 1
+1 15 1
+1 16 1
+1 17 1
+1 18 1
+1 19 1
+1 20 1
+1 80 1
+2 3 1
+2 4 1
+2 5 1
+2 6 1
+2 7 1
+2 8 1
+2 9 1
+2 10 1
+2 11 1
+2 12 1
+2 13 1
+2 14 1
+2 15 1
+2 16 1
+2 17 1
+2 18 1
+2 19 1
+2 20 1
+3 1 1
+3 2 1
+3 4 1
+3 5 1
+3 6 1
+3 7 1
+3 8 1
+3 9 1
+3 10 1
+3 11 1
+3 12 1
+3 13 1
+3 14 1
+3 15 1
+3 16 1
+3 17 1
+3 18 1
+3 19 1
+3 20 1
+4 1 1
+4 2 1
+4 3 1
+4 5 1
+4 6 1
+4 7 1
+4 8 1
+4 9 1
+4 10 1
+4 11 1
+4 12 1
+4 13 1
+4 14 1
+4 15 1
+4 16 1
+4 17 1
+4 18 1
+4 19 1
+4 20 1
+5 1 1
+5 2 1
+5 3 1
+5 4 1
+5 6 1
+5 7 1
+5 8 1
+5 9 1
+5 10 1
+5 11 1
+5 12 1
+5 13 1
+5 14 1
+5 15 1
+5 16 1
+5 17 1
+5 18 1
+5 19 1
+5 20 1
+6 1 1
+6 2 1
+6 3 1
+6 4 1
+6 5 1
+6 7 1
+6 8 1
+6 9 1
+6 10 1
+6 11 1
+6 12 1
+6 13 1
+6 14 1
+6 15 1
+6 16 1
+6 17 1
+6 18 1
+6 19 1
+6 20 1
+7 1 1
+7 2 1
+7 3 1
+7 4 1
+7 5 1
+7 6 1
+7 8 1
+7 9 1
+7 10 1
+7 11 1
+7 12 1
+7 13 1
+7 14 1
+7 15 1
+7 16 1
+7 17 1
+7 18 1
+7 19 1
+7 20 1
+8 1 1
+8 2 1
+8 3 1
+8 4 1
+8 5 1
+8 6 1
+8 7 1
+8 9 1
+8 10 1
+8 11 1
+8 12 1
+8 13 1
+8 14 1
+8 15 1
+8 16 1
+8 17 1
+8 18 1
+8 19 1
+8 20 1
+9 1 1
+9 2 1
+9 3 1
+9 4 1
+9 5 1
+9 6 1
+9 7 1
+9 8 1
+9 10 1
+9 11 1
+9 12 1
+9 13 1
+9 14 1
+9 15 1
+9 16 1
+9 17 1
+9 18 1
+9 19 1
+9 20 1
+10 1 1
+10 2 1
+10 3 1
+10 4 1
+10 5 1
+10 6 1
+10 7 1
+10 8 1
+10 9 1
+10 11 1
+10 12 1
+10 13 1
+10 14 1
+10 15 1
+10 16 1
+10 17 1
+10 18 1
+10 19 1
+10 20 1
+11 1 1
+11 2 1
+11 3 1
+11 4 1
+11 5 1
+11 6 1
+11 7 1
+11 8 1
+11 9 1
+11 10 1
+11 12 1
+11 13 1
+11 14 1
+11 15 1
+11 16 1
+11 17 1
+11 18 1
+11 19 1
+11 20 1
+12 1 1
+12 2 1
+12 3 1
+12 4 1
+12 5 1
+12 6 1
+12 7 1
+12 8 1
+12 9 1
+12 10 1
+12 11 1
+12 13 1
+12 14 1
+12 15 1
+12 16 1
+12 17 1
+12 18 1
+12 19 1
+12 20 1
+13 1 1
+13 2 1
+13 3 1
+13 4 1
+13 5 1
+13 6 1
+13 7 1
+13 8 1
+13 9 1
+13 10 1
+13 11 1
+13 12 1
+13 14 1
+13 15 1
+13 16 1
+13 17 1
+13 18 1
+13 19 1
+13 20 1
+14 1 1
+14 2 1
+14 3 1
+14 4 1
+14 5 1
+14 6 1
+14 7 1
+14 8 1
+14 9 1
+14 10 1
+14 11 1
+14 12 1
+14 13 1
+14 15 1
+14 16 1
+14 17 1
+14 18 1
+14 19 1
+14 20 1
+15 1 1
+15 2 1
+15 3 1
+15 4 1
+15 5 1
+15 6 1
+15 7 1
+15 8 1
+15 9 1
+15 10 1
+15 11 1
+15 12 1
+15 13 1
+15 14 1
+15 16 1
+15 17 1
+15 18 1
+15 19 1
+15 20 1
+16 1 1
+16 2 1
+16 3 1
+16 4 1
+16 5 1
+16 6 1
+16 7 1
+16 8 1
+16 9 1
+16 10 1
+16 11 1
+16 12 1
+16 13 1
+16 14 1
+16 15 1
+16 17 1
+16 18 1
+16 19 1
+16 20 1
+17 1 1
+17 2 1
+17 3 1
+17 4 1
+17 5 1
+17 6 1
+17 7 1
+17 8 1
+17 9 1
+17 10 1
+17 11 1
+17 12 1
+17 13 1
+17 14 1
+17 15 1
+17 16 1
+17 18 1
+17 19 1
+17 20 1
+18 1 1
+18 2 1
+18 3 1
+18 4 1
+18 5 1
+18 6 1
+18 7 1
+18 8 1
+18 9 1
+18 10 1
+18 11 1
+18 12 1
+18 13 1
+18 14 1
+18 15 1
+18 16 1
+18 17 1
+18 19 1
+18 20 1
+19 1 1
+19 2 1
+19 3 1
+19 4 1
+19 5 1
+19 6 1
+19 7 1
+19 8 1
+19 9 1
+19 10 1
+19 11 1
+19 12 1
+19 13 1
+19 14 1
+19 15 1
+19 16 1
+19 17 1
+19 18 1
+19 20 1
+20 1 1
+20 2 1
+20 3 1
+20 4 1
+20 5 1
+20 6 1
+20 7 1
+20 8 1
+20 9 1
+20 10 1
+20 11 1
+20 12 1
+20 13 1
+20 14 1
+20 15 1
+20 16 1
+20 17 1
+20 18 1
+20 19 1
+20 21 1
+21 20 1
+21 23 1
+21 24 1
+21 25 1
+21 26 1
+21 27 1
+21 28 1
+21 29 1
+21 30 1
+21 31 1
+21 32 1
+21 33 1
+21 34 1
+21 35 1
+21 36 1
+21 37 1
+21 38 1
+21 39 1
+21 40 1
+22 23 1
+22 24 1
+22 25 1
+22 26 1
+22 27 1
+22 28 1
+22 29 1
+22 30 1
+22 31 1
+22 32 1
+22 33 1
+22 34 1
+22 35 1
+22 36 1
+22 37 1
+22 38 1
+22 39 1
+22 40 1
+23 21 1
+23 22 1
+23 24 1
+23 25 1
+23 26 1
+23 27 1
+23 28 1
+23 29 1
+23 30 1
+23 31 1
+23 32 1
+23 33 1
+23 34 1
+23 35 1
+23 36 1
+23 37 1
+23 38 1
+23 39 1
+23 40 1
+24 21 1
+24 22 1
+24 23 1
+24 25 1
+24 26 1
+24 27 1
+24 28 1
+24 29 1
+24 30 1
+24 31 1
+24 32 1
+24 33 1
+24 34 1
+24 35 1
+24 36 1
+24 37 1
+24 38 1
+24 39 1
+24 40 1
+25 21 1
+25 22 1
+25 23 1
+25 24 1
+25 26 1
+25 27 1
+25 28 1
+25 29 1
+25 30 1
+25 31 1
+25 32 1
+25 33 1
+25 34 1
+25 35 1
+25 36 1
+25 37 1
+25 38 1
+25 39 1
+25 40 1
+26 21 1
+26 22 1
+26 23 1
+26 24 1
+26 25 1
+26 27 1
+26 28 1
+26 29 1
+26 30 1
+26 31 1
+26 32 1
+26 33 1
+26 34 1
+26 35 1
+26 36 1
+26 37 1
+26 38 1
+26 39 1
+26 40 1
+27 21 1
+27 22 1
+27 23 1
+27 24 1
+27 25 1
+27 26 1
+27 28 1
+27 29 1
+27 30 1
+27 31 1
+27 32 1
+27 33 1
+27 34 1
+27 35 1
+27 36 1
+27 37 1
+27 38 1
+27 39 1
+27 40 1
+28 21 1
+28 22 1
+28 23 1
+28 24 1
+28 25 1
+28 26 1
+28 27 1
+28 29 1
+28 30 1
+28 31 1
+28 32 1
+28 33 1
+28 34 1
+28 35 1
+28 36 1
+28 37 1
+28 38 1
+28 39 1
+28 40 1
+29 21 1
+29 22 1
+29 23 1
+29 24 1
+29 25 1
+29 26 1
+29 27 1
+29 28 1
+29 30 1
+29 31 1
+29 32 1
+29 33 1
+29 34 1
+29 35 1
+29 36 1
+29 37 1
+29 38 1
+29 39 1
+29 40 1
+30 21 1
+30 22 1
+30 23 1
+30 24 1
+30 25 1
+30 26 1
+30 27 1
+30 28 1
+30 29 1
+30 31 1
+30 32 1
+30 33 1
+30 34 1
+30 35 1
+30 36 1
+30 37 1
+30 38 1
+30 39 1
+30 40 1
+31 21 1
+31 22 1
+31 23 1
+31 24 1
+31 25 1
+31 26 1
+31 27 1
+31 28 1
+31 29 1
+31 30 1
+31 32 1
+31 33 1
+31 34 1
+31 35 1
+31 36 1
+31 37 1
+31 38 1
+31 39 1
+31 40 1
+32 21 1
+32 22 1
+32 23 1
+32 24 1
+32 25 1
+32 26 1
+32 27 1
+32 28 1
+32 29 1
+32 30 1
+32 31 1
+32 33 1
+32 34 1
+32 35 1
+32 36 1
+32 37 1
+32 38 1
+32 39 1
+32 40 1
+33 21 1
+33 22 1
+33 23 1
+33 24 1
+33 25 1
+33 26 1
+33 27 1
+33 28 1
+33 29 1
+33 30 1
+33 31 1
+33 32 1
+33 34 1
+33 35 1
+33 36 1
+33 37 1
+33 38 1
+33 39 1
+33 40 1
+34 21 1
+34 22 1
+34 23 1
+34 24 1
+34 25 1
+34 26 1
+34 27 1
+34 28 1
+34 29 1
+34 30 1
+34 31 1
+34 32 1
+34 33 1
+34 35 1
+34 36 1
+34 37 1
+34 38 1
+34 39 1
+34 40 1
+35 21 1
+35 22 1
+35 23 1
+35 24 1
+35 25 1
+35 26 1
+35 27 1
+35 28 1
+35 29 1
+35 30 1
+35 31 1
+35 32 1
+35 33 1
+35 34 1
+35 36 1
+35 37 1
+35 38 1
+35 39 1
+35 40 1
+36 21 1
+36 22 1
+36 23 1
+36 24 1
+36 25 1
+36 26 1
+36 27 1
+36 28 1
+36 29 1
+36 30 1
+36 31 1
+36 32 1
+36 33 1
+36 34 1
+36 35 1
+36 37 1
+36 38 1
+36 39 1
+36 40 1
+37 21 1
+37 22 1
+37 23 1
+37 24 1
+37 25 1
+37 26 1
+37 27 1
+37 28 1
+37 29 1
+37 30 1
+37 31 1
+37 32 1
+37 33 1
+37 34 1
+37 35 1
+37 36 1
+37 38 1
+37 39 1
+37 40 1
+38 21 1
+38 22 1
+38 23 1
+38 24 1
+38 25 1
+38 26 1
+38 27 1
+38 28 1
+38 29 1
+38 30 1
+38 31 1
+38 32 1
+38 33 1
+38 34 1
+38 35 1
+38 36 1
+38 37 1
+38 39 1
+38 40 1
+39 21 1
+39 22 1
+39 23 1
+39 24 1
+39 25 1
+39 26 1
+39 27 1
+39 28 1
+39 29 1
+39 30 1
+39 31 1
+39 32 1
+39 33 1
+39 34 1
+39 35 1
+39 36 1
+39 37 1
+39 38 1
+39 40 1
+40 21 1
+40 22 1
+40 23 1
+40 24 1
+40 25 1
+40 26 1
+40 27 1
+40 28 1
+40 29 1
+40 30 1
+40 31 1
+40 32 1
+40 33 1
+40 34 1
+40 35 1
+40 36 1
+40 37 1
+40 38 1
+40 39 1
+40 41 1
+41 40 1
+41 43 1
+41 44 1
+41 45 1
+41 46 1
+41 47 1
+41 48 1
+41 49 1
+41 50 1
+41 51 1
+41 52 1
+41 53 1
+41 54 1
+41 55 1
+41 56 1
+41 57 1
+41 58 1
+41 59 1
+41 60 1
+42 43 1
+42 44 1
+42 45 1
+42 46 1
+42 47 1
+42 48 1
+42 49 1
+42 50 1
+42 51 1
+42 52 1
+42 53 1
+42 54 1
+42 55 1
+42 56 1
+42 57 1
+42 58 1
+42 59 1
+42 60 1
+43 41 1
+43 42 1
+43 44 1
+43 45 1
+43 46 1
+43 47 1
+43 48 1
+43 49 1
+43 50 1
+43 51 1
+43 52 1
+43 53 1
+43 54 1
+43 55 1
+43 56 1
+43 57 1
+43 58 1
+43 59 1
+43 60 1
+44 41 1
+44 42 1
+44 43 1
+44 45 1
+44 46 1
+44 47 1
+44 48 1
+44 49 1
+44 50 1
+44 51 1
+44 52 1
+44 53 1
+44 54 1
+44 55 1
+44 56 1
+44 57 1
+44 58 1
+44 59 1
+44 60 1
+45 41 1
+45 42 1
+45 43 1
+45 44 1
+45 46 1
+45 47 1
+45 48 1
+45 49 1
+45 50 1
+45 51 1
+45 52 1
+45 53 1
+45 54 1
+45 55 1
+45 56 1
+45 57 1
+45 58 1
+45 59 1
+45 60 1
+46 41 1
+46 42 1
+46 43 1
+46 44 1
+46 45 1
+46 47 1
+46 48 1
+46 49 1
+46 50 1
+46 51 1
+46 52 1
+46 53 1
+46 54 1
+46 55 1
+46 56 1
+46 57 1
+46 58 1
+46 59 1
+46 60 1
+47 41 1
+47 42 1
+47 43 1
+47 44 1
+47 45 1
+47 46 1
+47 48 1
+47 49 1
+47 50 1
+47 51 1
+47 52 1
+47 53 1
+47 54 1
+47 55 1
+47 56 1
+47 57 1
+47 58 1
+47 59 1
+47 60 1
+48 41 1
+48 42 1
+48 43 1
+48 44 1
+48 45 1
+48 46 1
+48 47 1
+48 49 1
+48 50 1
+48 51 1
+48 52 1
+48 53 1
+48 54 1
+48 55 1
+48 56 1
+48 57 1
+48 58 1
+48 59 1
+48 60 1
+49 41 1
+49 42 1
+49 43 1
+49 44 1
+49 45 1
+49 46 1
+49 47 1
+49 48 1
+49 50 1
+49 51 1
+49 52 1
+49 53 1
+49 54 1
+49 55 1
+49 56 1
+49 57 1
+49 58 1
+49 59 1
+49 60 1
+50 41 1
+50 42 1
+50 43 1
+50 44 1
+50 45 1
+50 46 1
+50 47 1
+50 48 1
+50 49 1
+50 51 1
+50 52 1
+50 53 1
+50 54 1
+50 55 1
+50 56 1
+50 57 1
+50 58 1
+50 59 1
+50 60 1
+51 41 1
+51 42 1
+51 43 1
+51 44 1
+51 45 1
+51 46 1
+51 47 1
+51 48 1
+51 49 1
+51 50 1
+51 52 1
+51 53 1
+51 54 1
+51 55 1
+51 56 1
+51 57 1
+51 58 1
+51 59 1
+51 60 1
+52 41 1
+52 42 1
+52 43 1
+52 44 1
+52 45 1
+52 46 1
+52 47 1
+52 48 1
+52 49 1
+52 50 1
+52 51 1
+52 53 1
+52 54 1
+52 55 1
+52 56 1
+52 57 1
+52 58 1
+52 59 1
+52 60 1
+53 41 1
+53 42 1
+53 43 1
+53 44 1
+53 45 1
+53 46 1
+53 47 1
+53 48 1
+53 49 1
+53 50 1
+53 51 1
+53 52 1
+53 54 1
+53 55 1
+53 56 1
+53 57 1
+53 58 1
+53 59 1
+53 60 1
+54 41 1
+54 42 1
+54 43 1
+54 44 1
+54 45 1
+54 46 1
+54 47 1
+54 48 1
+54 49 1
+54 50 1
+54 51 1
+54 52 1
+54 53 1
+54 55 1
+54 56 1
+54 57 1
+54 58 1
+54 59 1
+54 60 1
+55 41 1
+55 42 1
+55 43 1
+55 44 1
+55 45 1
+55 46 1
+55 47 1
+55 48 1
+55 49 1
+55 50 1
+55 51 1
+55 52 1
+55 53 1
+55 54 1
+55 56 1
+55 57 1
+55 58 1
+55 59 1
+55 60 1
+56 41 1
+56 42 1
+56 43 1
+56 44 1
+56 45 1
+56 46 1
+56 47 1
+56 48 1
+56 49 1
+56 50 1
+56 51 1
+56 52 1
+56 53 1
+56 54 1
+56 55 1
+56 57 1
+56 58 1
+56 59 1
+56 60 1
+57 41 1
+57 42 1
+57 43 1
+57 44 1
+57 45 1
+57 46 1
+57 47 1
+57 48 1
+57 49 1
+57 50 1
+57 51 1
+57 52 1
+57 53 1
+57 54 1
+57 55 1
+57 56 1
+57 58 1
+57 59 1
+57 60 1
+58 41 1
+58 42 1
+58 43 1
+58 44 1
+58 45 1
+58 46 1
+58 47 1
+58 48 1
+58 49 1
+58 50 1
+58 51 1
+58 52 1
+58 53 1
+58 54 1
+58 55 1
+58 56 1
+58 57 1
+58 59 1
+58 60 1
+59 41 1
+59 42 1
+59 43 1
+59 44 1
+59 45 1
+59 46 1
+59 47 1
+59 48 1
+59 49 1
+59 50 1
+59 51 1
+59 52 1
+59 53 1
+59 54 1
+59 55 1
+59 56 1
+59 57 1
+59 58 1
+59 60 1
+60 41 1
+60 42 1
+60 43 1
+60 44 1
+60 45 1
+60 46 1
+60 47 1
+60 48 1
+60 49 1
+60 50 1
+60 51 1
+60 52 1
+60 53 1
+60 54 1
+60 55 1
+60 56 1
+60 57 1
+60 58 1
+60 59 1
+60 61 1
+61 60 1
+61 63 1
+61 64 1
+61 65 1
+61 66 1
+61 67 1
+61 68 1
+61 69 1
+61 70 1
+61 71 1
+61 72 1
+61 73 1
+61 74 1
+61 75 1
+61 76 1
+61 77 1
+61 78 1
+61 79 1
+61 80 1
+62 63 1
+62 64 1
+62 65 1
+62 66 1
+62 67 1
+62 68 1
+62 69 1
+62 70 1
+62 71 1
+62 72 1
+62 73 1
+62 74 1
+62 75 1
+62 76 1
+62 77 1
+62 78 1
+62 79 1
+62 80 1
+63 61 1
+63 62 1
+63 64 1
+63 65 1
+63 66 1
+63 67 1
+63 68 1
+63 69 1
+63 70 1
+63 71 1
+63 72 1
+63 73 1
+63 74 1
+63 75 1
+63 76 1
+63 77 1
+63 78 1
+63 79 1
+63 80 1
+64 61 1
+64 62 1
+64 63 1
+64 65 1
+64 66 1
+64 67 1
+64 68 1
+64 69 1
+64 70 1
+64 71 1
+64 72 1
+64 73 1
+64 74 1
+64 75 1
+64 76 1
+64 77 1
+64 78 1
+64 79 1
+64 80 1
+65 61 1
+65 62 1
+65 63 1
+65 64 1
+65 66 1
+65 67 1
+65 68 1
+65 69 1
+65 70 1
+65 71 1
+65 72 1
+65 73 1
+65 74 1
+65 75 1
+65 76 1
+65 77 1
+65 78 1
+65 79 1
+65 80 1
+66 61 1
+66 62 1
+66 63 1
+66 64 1
+66 65 1
+66 67 1
+66 68 1
+66 69 1
+66 70 1
+66 71 1
+66 72 1
+66 73 1
+66 74 1
+66 75 1
+66 76 1
+66 77 1
+66 78 1
+66 79 1
+66 80 1
+67 61 1
+67 62 1
+67 63 1
+67 64 1
+67 65 1
+67 66 1
+67 68 1
+67 69 1
+67 70 1
+67 71 1
+67 72 1
+67 73 1
+67 74 1
+67 75 1
+67 76 1
+67 77 1
+67 78 1
+67 79 1
+67 80 1
+68 61 1
+68 62 1
+68 63 1
+68 64 1
+68 65 1
+68 66 1
+68 67 1
+68 69 1
+68 70 1
+68 71 1
+68 72 1
+68 73 1
+68 74 1
+68 75 1
+68 76 1
+68 77 1
+68 78 1
+68 79 1
+68 80 1
+69 61 1
+69 62 1
+69 63 1
+69 64 1
+69 65 1
+69 66 1
+69 67 1
+69 68 1
+69 70 1
+69 71 1
+69 72 1
+69 73 1
+69 74 1
+69 75 1
+69 76 1
+69 77 1
+69 78 1
+69 79 1
+69 80 1
+70 61 1
+70 62 1
+70 63 1
+70 64 1
+70 65 1
+70 66 1
+70 67 1
+70 68 1
+70 69 1
+70 71 1
+70 72 1
+70 73 1
+70 74 1
+70 75 1
+70 76 1
+70 77 1
+70 78 1
+70 79 1
+70 80 1
+71 61 1
+71 62 1
+71 63 1
+71 64 1
+71 65 1
+71 66 1
+71 67 1
+71 68 1
+71 69 1
+71 70 1
+71 72 1
+71 73 1
+71 74 1
+71 75 1
+71 76 1
+71 77 1
+71 78 1
+71 79 1
+71 80 1
+72 61 1
+72 62 1
+72 63 1
+72 64 1
+72 65 1
+72 66 1
+72 67 1
+72 68 1
+72 69 1
+72 70 1
+72 71 1
+72 73 1
+72 74 1
+72 75 1
+72 76 1
+72 77 1
+72 78 1
+72 79 1
+72 80 1
+73 61 1
+73 62 1
+73 63 1
+73 64 1
+73 65 1
+73 66 1
+73 67 1
+73 68 1
+73 69 1
+73 70 1
+73 71 1
+73 72 1
+73 74 1
+73 75 1
+73 76 1
+73 77 1
+73 78 1
+73 79 1
+73 80 1
+74 61 1
+74 62 1
+74 63 1
+74 64 1
+74 65 1
+74 66 1
+74 67 1
+74 68 1
+74 69 1
+74 70 1
+74 71 1
+74 72 1
+74 73 1
+74 75 1
+74 76 1
+74 77 1
+74 78 1
+74 79 1
+74 80 1
+75 61 1
+75 62 1
+75 63 1
+75 64 1
+75 65 1
+75 66 1
+75 67 1
+75 68 1
+75 69 1
+75 70 1
+75 71 1
+75 72 1
+75 73 1
+75 74 1
+75 76 1
+75 77 1
+75 78 1
+75 79 1
+75 80 1
+76 61 1
+76 62 1
+76 63 1
+76 64 1
+76 65 1
+76 66 1
+76 67 1
+76 68 1
+76 69 1
+76 70 1
+76 71 1
+76 72 1
+76 73 1
+76 74 1
+76 75 1
+76 77 1
+76 78 1
+76 79 1
+76 80 1
+77 61 1
+77 62 1
+77 63 1
+77 64 1
+77 65 1
+77 66 1
+77 67 1
+77 68 1
+77 69 1
+77 70 1
+77 71 1
+77 72 1
+77 73 1
+77 74 1
+77 75 1
+77 76 1
+77 78 1
+77 79 1
+77 80 1
+78 61 1
+78 62 1
+78 63 1
+78 64 1
+78 65 1
+78 66 1
+78 67 1
+78 68 1
+78 69 1
+78 70 1
+78 71 1
+78 72 1
+78 73 1
+78 74 1
+78 75 1
+78 76 1
+78 77 1
+78 79 1
+78 80 1
+79 61 1
+79 62 1
+79 63 1
+79 64 1
+79 65 1
+79 66 1
+79 67 1
+79 68 1
+79 69 1
+79 70 1
+79 71 1
+79 72 1
+79 73 1
+79 74 1
+79 75 1
+79 76 1
+79 77 1
+79 78 1
+79 80 1
+80 1 1
+80 61 1
+80 62 1
+80 63 1
+80 64 1
+80 65 1
+80 66 1
+80 67 1
+80 68 1
+80 69 1
+80 70 1
+80 71 1
+80 72 1
+80 73 1
+80 74 1
+80 75 1
+80 76 1
+80 77 1
+80 78 1
+80 79 1
diff --git a/src/test/resources/datasets/caveman_4_20.ijv.mtd
b/src/test/resources/datasets/caveman_4_20.ijv.mtd
new file mode 100644
index 0000000..69d3c0d
--- /dev/null
+++ b/src/test/resources/datasets/caveman_4_20.ijv.mtd
@@ -0,0 +1,7 @@
+{
+ "data_type": "matrix",
+ "value_type": "double",
+ "rows": 80,
+ "cols": 80,
+ "format": "text",
+}
\ No newline at end of file
diff --git a/src/test/scripts/functions/builtin/deepWalk.dml
b/src/test/scripts/functions/builtin/deepWalk.dml
new file mode 100644
index 0000000..fa17aac
--- /dev/null
+++ b/src/test/scripts/functions/builtin/deepWalk.dml
@@ -0,0 +1,25 @@
+#-------------------------------------------------------------
+#
+# Licensed to the Apache Software Foundation (ASF) under one
+# or more contributor license agreements. See the NOTICE file
+# distributed with this work for additional information
+# regarding copyright ownership. The ASF licenses this file
+# to you under the Apache License, Version 2.0 (the
+# "License"); you may not use this file except in compliance
+# with the License. You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing,
+# software distributed under the License is distributed on an
+# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+# KIND, either express or implied. See the License for the
+# specific language governing permissions and limitations
+# under the License.
+#
+#-------------------------------------------------------------
+
+Graph = read($GRAPH)
+Phi = deepWalk(Graph=Graph, w=$WINDOW_SIZE, d=$EMBEDDING_SIZE,
gamma=$WALKS_PER_VERTEX, t=$WALK_LENGTH)
+
+write(Phi, $OUT_FILE)
