Article Preview
TopIntroduction
Graph, a form of structured data, allows for the modeling of complex relationships among objects. In recent years, more and more data are modeled as graphs and such data is ubiquitous in social networks, biology, chemistry, computer vision, and other domains (Cai et al., 2018, 2021; L. Li et al., 2019; Yanardag & Vishwanathan, 2015b). For example, graphs can be derived from interactions between groups of people, such as friendships on a social website, or collaborations in a network of actors or scientists. In biochemistry, molecular compounds can be modeled as graphs with vertices corresponding to atoms and the edges to chemical bonds (Vishwanathan et al., 2010).
The problem of accurately measuring the similarity between graphs is at the core of many applications(Peng et al., 2022). As the demand for structured data analysis grows, the problem of graph classification has been widely studied in these domains. For example, in protein function prediction, it is a common task to determine whether a protein is an enzyme or a non-enzyme (Borgwardt & Kriegel, 2005). A similar task on a collaboration dataset is to predict which genre an ego-network of an actor/actress belongs to (Yanardag & Vishwanathan, 2015b). Since there are many ways to represent images as graphs, many computers vision tasks, such as classifying images(Tian & Han, 2022), can also be considered as graph classification problems.
To date, the kernel methods are one of the most popular methods for comparing similarities between structured objects, especially in the domain of graph classification. Graph kernels have achieved state-of-the-art results on many graph datasets. In general, the kernel methods utilize a positive semidefinite kernel function to measure the similarity between two objects, which can be expressed as an inner product in reproducing kernel Hilbert space 
(Schölkopf & Smola, 2001). Some graph kernels are computed based on local properties, such as the neighborhood features of vertices (Hido & Kashima, 2009), or some small substructures of graphs (i.e., trees, cycles, graphlets) (Horváth et al., 2004; Orsini et al., 2015; Shervashidze et al., 2009, 2011). There are also some graph kernels built from a global perspective and they focus on the global properties of graphs (Kang et al., 2012; Nikolentzos et al., 2017; Wu et al., 2019). Most of the existing graph kernels cannot capture graph similarity at multiple levels of scale. The Multiscale Laplacian Graph Kernel (Kondor & Pan, 2016) is the first graph kernel that can compare graphs at multiple different scales, by building a hierarchy of nested subgraphs. However, it requires Laplacian matrix operations on the graph and thus has a very high runtime.