Heat Kernel Diffusion Step

Problem

Perform one explicit Euler step of heat diffusion on an undirected graph: x' = x - tau * L x, where L is the Laplacian and tau is the step size.

Return the updated signal in node order. edges is a list of [u, v] pairs, signal is the current value at each node, and tau is the step size.

Hint

Constant signals are stationary because the Laplacian annihilates them.

case 1

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

expected: [0,0.5,0,0.5]

case 2

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

expected: [1,1,1]

case 3

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

expected: [2.5,3.5]

Starter codePython

def heat_kernel_step(n, edges, signal, tau):
    # Your code here
    pass

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