To find communities in \(G\) , we use the common Infomap algorithm [1]} as it works with weighted graphs and scales linearly with \(|E|\) .
It works by leveraging an information-theoretic definition of network communities:
Random walks sample information flow in networks and inform the construction a map \(\Theta _K\)  from nodes to \(M\)  communities minimizing the expected description length of a random walk.
With the discrete many-to-one mapping \(\Theta _K: V \rightarrow \lbrace 1, \dots , M\rbrace \)  obtained from Infomap and computed on train data, we merge the clusters of the validation data to the desired number of ground-truth classes and do Hungarian matching [2]}.
Note that Hungarian matching does not extract any meaningful label information; it merely makes the evaluation metric permutation-invariant [3]}.
