Random Walk Graph Kernel Count

Problem

Count all walks of length at most k in an undirected graph with n nodes.

The number of walks of length t is the sum of all entries of A^t, where A is the adjacency matrix. Starting with the n walks of length 0, repeatedly multiply the all-ones vector by A and accumulate. Return the total count.

Hint

The walk kernel compares graphs by counting matching paths, a classic structural kernel.

Test cases

case 1

in: [3,[[0,1],[1,2],[2,0]],2]

expected: 21

case 2

in: [3,[[0,1],[1,2]],3]

expected: 21

case 3

in: [2,[[0,1]],0]

expected: 2

case 4

in: [2,[[0,1]],1]

expected: 4

Starter codePython

def random_walk_kernel_count(n, edges, k):
    # Your code here
    pass

4 test cases · run your code against them in the editor