Computational complexity of massage passing and aggregation

[zcaicaros]

Hi, I am just wondering what computational complexity of message passing and aggregation is.

Suppose I have a graph G=(V, E), |V|=n, if I perform one message passing on this graph then aggregate the message using either max, mean or sum, will the complexity be O(1)? Because no matter how many nodes are there in a graph, the scope of the computation is focusing on each single node, i.e., each node will receive message from its neighbours and aggregates them in the same way.

[rusty1s]

The complexity of a single round of message passing is O(E), since a message is send to a node for each edge in your graph. Although on GPUs we parallelize computation across the edge dimension, this does not change the theoretical time complexity of message passing (only the practical runtime).

[zcaicaros]

Right. I was confused by parallel computation.