Descriptive Kernel Convolution Network with Improved Random Walk Kernel
Meng-Chieh Lee Lingxiao Zhao Leman Akoglu
Graph kernels used to be the dominant approach to feature engineering for
structured data, which are superseded by modern GNNs as the former lacks
learnability. Recently, a suite of Kernel Convolution Networks (KCNs)
successfully revitalized graph kernels by introducing learnability, which
convolves input with learnable hidden graphs using a certain graph kernel. The
random walk kernel (RWK) has been used as the default kernel in many KCNs,
gaining increasing attention. In this paper, we first revisit the RWK and its
current usage in KCNs, revealing several shortcomings of the existing designs,
and propose an improved graph kernel RWK+, by introducing color-matching random
walks and deriving its efficient computation. We then propose RWK+CN, a KCN
that uses RWK+ as the core kernel to learn descriptive graph features with an
unsupervised objective, which can not be achieved by GNNs. Further, by
unrolling RWK+, we discover its connection with a regular GCN layer, and
propose a novel GNN layer RWK+Conv. In the first part of experiments, we
demonstrate the descriptive learning ability of RWK+CN with the improved random
walk kernel RWK+ on unsupervised pattern mining tasks; in the second part, we
show the effectiveness of RWK+ for a variety of KCN architectures and
supervised graph learning tasks, and demonstrate the expressiveness of RWK+Conv
layer, especially on the graph-level tasks. RWK+ and RWK+Conv adapt to various
real-world applications, including web applications such as bot detection in a
web-scale Twitter social network, and community classification in Reddit social
interaction networks.