Appendix Expanded

Notable instances of this architecture include, e.g., [33,37,51,105],and the spectral approaches proposed in, e.g., [14, 29, 64, 81]--all of which descend from early work in [65, 80, 102, 97]. Fork =1,the power ofthe algorithm has been completely characterized [4,63]. In general, a different mappingM()could be used, depending on the neighborhood information that we would like to aggregate. The following result relates the power of thek-WLandδ-k-WL. Proposition1(restated, Proposition 1 in the main text).