A Persistent Weisfeiler--Lehman Procedure for Graph Classification

Inspired by the Weisfeiler--Lehman graph kernel, we augment its iterative feature map construction approach by a set of multi-scale topological features. More precisely, we leverage propagated node label information to transform an unweighted graph into a metric one. We then use persistent homology, a technique from topological data analysis, to assess the topological properties, i.e. connected components and cycles, of the metric graph. Through this process, each graph can be represented similarly to the original Weisfeiler--Lehman sub-tree feature map.

We demonstrate the utility and improved accuracy of our method on numerous graph data sets while also discussing theoretical aspects of our approach.