The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs

This simple algorithm is already quite powerful in distinguishing non-isomorphic graphs [Babai et al., 1980], and In recent years, algorithms and neural architectures has been therefore applied in many areas [Grohe et al., 2014; based on the Weisfeiler-Leman algorithm, a wellknown Kersting et al., 2014; Li et al., 2016; Yao and Holder, 2015; heuristic for the graph isomorphism problem, Zhang and Chen, 2017]. On the other hand, it is easy to see that emerged as a powerful tool for (supervised) machine the algorithm cannot distinguish all non-isomorphic graphs [Cai learning with graphs and relational data. Here, we give et al., 1992]. For example, it cannot distinguish graphs with different a comprehensive overview of the algorithm's use in a triangle counts, cf. Figure 1, which is an important feature machine learning setting. We discuss the theoretical in social network analysis. Therefore, it has been generalized to background, show how to use it for supervised graphand k-tuples leading to a more powerful graph isomorphism heuristic, node classification, discuss recent extensions, and which has been investigated in depth by the theoretical computer its connection to neural architectures. Moreover, we science community [Cai et al., 1992; Kiefer and Schweitzer, 2016; give an overview of current applications and future Babai, 2016; Grohe, 2017]. In Shervashidze et al. [2011], the directions to stimulate research.