Propagation kernels: efficient graph kernels from propagated information

By Marion Neumann, Roman Garnett, Christian Bauckhage, Kristian Kersting. 2014

303 citations recorded by the source corpus.

We introduce propagation kernels, a general graph-kernel framework for efficiently measuring the similarity of structured data. Propagation kernels are based on monitoring how information spreads through a set of given graphs. They leverage early-stage distributions from propagation schemes such as random walks to capture structural information encoded in node labels, attributes, and edge information. This has two benefits. First, off-the-shelf propagation schemes can be used to naturally construct kernels for many graph types, including labeled, partially labeled, unlabeled, directed, and attributed graphs. Second, by leveraging existing efficient and informative propagation schemes, propagation kernels can be considerably faster than state-of-the-art approaches without sacrificing predictive performance. We will also show that if the graphs at hand have a regular structure, for instance when modeling image or video data, one can exploit this regularity to scale the kernel computation to large databases of graphs with thousands of nodes. We support our contributions by exhaustive experiments on a number of real-world graphs from a variety of application domains.

Subfields: Artificial Intelligence, Computer Networks and Communications, Graph Learning, Algorithms & Complexity, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Graph Learning

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

Pre-training Graph Neural Networks with Kernels (2018, neutral): “More recent frameworks for graph kernels addressing efﬁciency or efﬁcacy have been proposed in Neumann et al. [2015]; Orsini et al. [2015].”
An End-to-End Deep Learning Architecture for Graph Classification (2018, background): “Connection with propagation kernel Instead of operating on integer node labels, the propagation kernel (PK) (Neumann et al. 2012; 2016) compares the label distributions between two graphs.”
Covariant Compositional Networks For Learning Graphs (2018, background): “…artner, 2002; Borgwardt & Kriegel, 2005; Feragen et al., 2013), counting subgraphs (Shervashidze et al., 2009), spectral ideas (Vishwanathan et al., 2010), label propagation schemes with hashing (Shervashidze et al., 2011; Neumann et al., 2016), and even algebraic ideas (Kondor & Borgwardt, 2008).”
Provably Powerful Graph Networks (2019, neutral): “1 > 3 days NA NA NA NA PK (Neumann et al., 2016) 76±2.”
The Multiscale Laplacian Graph Kernel (2016, background): “Two notable exceptions are the Weisfeiler–Lehman kernel [10] and Propagation Kernel [11].”
A Degeneracy Framework for Graph Similarity (2018, methodology): “Two well-known kernels that account for that are the Weisfeiler–Lehman sub-tree kernel [Shervashidze et al. , 2011] and the propagation kernel [Neumann et al. , 2016].”
Invariant and Equivariant Graph Networks (2018, methodology): “(2017); Qi et al. (2017). These works characterize all linear permutation invariant and equivariant operators acting on node-value (i.”
Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks (2021, methodology): “…of SIN are reported in Table 2, along with those of graph kernel methods (RWK (Gärtner et al., 2003), GK (Shervashidze et al., 2009), PK (Neumann et al., 2016), WL kernel (Shervashidze et al., 2011)) and other GNNs (DCNN (Atwood & Towsley, 2016), DGCNN (Zhang et al., 2018), IGN (Maron…”
TUDataset: A collection of benchmark datasets for learning with graphs (2020, unknown): “Other datasets represent C UNEIFORM signs (Kriege et al., 2018a), 3D point clouds for robot grasping tasks (F IRST MM_DB) and semantic image processing (M SRC ) (Neumann et al., 2016).”
Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs (2017, background): “, see [17], [35], [36], and most notably the Weisfeiler-Lehman subtree kernel [3].”
Optimal Transport for structured data with application on graphs (2018, methodology): “For real valued vector attributes, we consider the HOP-PER kernel (HOPPERK) (Feragen et al., 2013) and the propagation kernel (PROPAK) (Neumann et al., 2016).”
Tree-Based Kernel for Graphs With Continuous Attributes (2015, methodology): “presented in Section V-C, the Propagation kernel ( P2K) [11], different instantiations of the Graph Invariant Kernels [1 2] (GIK NSPDK, GIK SGK GLOBAL, GIK SGK LOCAL, GIK WL GLOBAL, GIK WL LOCAL) and the results from the paper [10], corrected according to the erratum.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, unknown): “, 2009), PK (Neumann et al., 2016), DCNN (Atwood & Towsley, 2016) and DGCNN (Zhang et al.”
Implicit Graph Neural Networks (2020, background): “…Network ( GIN ) (Xu et al., 2018), and a number of state-of-the-art graph kernels: Graphlet Kernel ( GK ) (Shervashidze et al., 2009), Random-walk Kernel ( RW ) (Gärtner et al., 2003), Propagation Kernel ( PK ) (Neumann et al., 2016) and Weisfeiler-Lehman Kernel ( WL ) (Shervashidze et al., 2011).”
Substructure Assembling Network for Graph Classification (2018, background): “Another popular approach is to design graph kernels to measure the similarity between graphs (Neumann et al. 2016), followed by a kernel-based classifier.”
A survey on graph kernels (2019, methodology): “…5, 10 dimensions) 5 , the DBR kernel of Bai et al. (2014) (no parameters, code obtained through correspondence) and the propagation kernel (Prop) (Neumann et al. 2016; Neumann 2016) for which we select the number of diffusion iterations by cross-validation and use the settings recommended by the…”