RetGK: Graph Kernels based on Return Probabilities of Random Walks

1 Introduction

• Graph kernels compare graph connectivity and attributes, but must address isomorphism invariance, attribute integration, and scalability to graphs with millions of nodes.The introduction frames these as three technical challenges for effective graph kernels.Source: §1 · p. 1
• RetGK represents nodes with return probability features, embeds attributed and nonattributed graphs in a Hilbert space, and uses approximate feature maps to construct efficient kernels.The method is presented as a way to address the introduction’s kernel-design challenges.Source: §1 · p. 1

2.1 Graph concepts

• Graphs are modeled with nodes and weighted edges, with node attributes that may be discrete or continuous.For unweighted graphs, edge weights are set to one.Source: §2.1 · p. 2

2.2 Tensor algebra

• A tensor is a multidimensional array with multiple indices, and vectors and matrices are first- and second-order examples.The paper uses tensor algebra in its approximate graph embeddings.Source: §2.2 · p. 2

3 Return Probabilities of Random Walks

• Return probability features (RPFs) encode each node’s return probabilities across walk lengths, representing a graph as a set of node feature vectors.This node-based representation avoids directly comparing transition matrices whose sizes and row or column correspondences may differ.Source: §3 · p. 3

3.1 The properties of RPF

• Isomorphic graphs have the same RPF sets, and differing RPF sets can rule out isomorphism and enable structural-role comparisons without node matching.The passage states that equal RPF sets are necessary for isomorphic graphs; it does not establish the converse.Source: §3.1 · p. 3
• As walk length increases, return probabilities capture interactions with larger subgraphs, but eventually converge toward stationary probabilities and add little new information.The paper notes that sufficiently large steps provide little additional RPF information.Source: §3.1 · p. 3
• For connected graphs of equal size and volume, identical RPF sets are associated with similar spectral properties.The paper relates RPFs to spectral representations containing almost all graph-structure information.Source: §3.1 · p. 3
• The three center nodes’ return probabilities are plotted over 1–200 steps; C1 and C2 remain close through step eight, while C3 deviates earlier.Their first two return probabilities match because they and their neighbors have the same degrees.Source: §3.1 · p. 3, Figure 1 · p. 4

G and RPFS

• RPFs for step lengths S ≥ n are the same, consistent with the observation that very large walk steps add little new information.The passage links this result to the earlier discussion of large random-walk steps.Source: G and RPFS · p. 4

3.2 The computation of RPF

• Brute-force computation requires repeated n × n matrix multiplication and has time complexity (S − 1)n^3.The paper instead exploits the fact that only transition-matrix diagonal terms are needed; its eigen-based method computes the eigendecomposition in O(n^3) and subsequent quantities in O(n^2).Source: §3.2 · p. 4

3.2.1 Monte Carlo simulation method

• For graphs with more than 10^5 nodes, the paper proposes parallelizable Monte Carlo walks to estimate return probabilities from return frequencies.For each node it simulates M walks of length S and estimates each step’s return probability by the relative frequency of returning to the start.Source: §3.2.1 · p. 4

4 Hilbert space embeddings of graphs

• Return-probability features act as structural-role attributes, allowing attributed and nonattributed graphs to share one representation.The representation combines structural roles with measured node attributes; without measured attributes, it reduces to the nonattributed case.Source: §4 · p. 5
• The node-set representation forms an empirical distribution that can be embedded in a reproducing kernel Hilbert space by kernel mean embedding.Source: §4 · p. 5

4.1 Graph kernels (I)

• The section generalizes positive-definite kernels to graphs by defining graph kernels on their Hilbert-space embeddings.Source: §4.1 · p. 5

5 Approximated Hilbert space embedding of graphs

• Exact graph-kernel comparisons scale quadratically with node counts, motivating approximate explicit feature maps for larger datasets.Source: §5 · pp. 5–6
• As feature dimensions increase, the inner product between approximate graph embeddings converges to the exact Hilbert-space inner product.Source: §5 · p. 6

5.1 Graph Kernels (II)

• The approximate tensor embeddings yield positive-definite graph kernels that converge to K1 and K2 as feature dimensions increase.Source: §5.1 · p. 6
• The tensor representation size does not depend on node counts, so kernel computation uses vector inner products or distances and scales to large graphs.Source: §5.1 · p. 6

6.1 Datasets

• The 21 benchmarks cover unlabeled graphs, graphs with discrete or continuous attributes, and graphs with both attribute types.Datasets include social networks, proteins, chemical compounds, and synthetic graphs.Source: §6.1 · pp. 6–7

6.2 Experimental setup

• The evaluation tests RetGKI, RetGKII, and RetGKII(MC) against eight listed methods using SVM classification and repeated 10-fold cross-validation.RetGKII(MC) uses 200 Monte Carlo trials; isolated nodes receive artificial self-loops, and results report average accuracy and standard errors.Source: §6.2 · p. 7

6.3 Experimental Results

• On large social-network datasets, RetGKII(MC) is almost one order of magnitude faster than the Weisfeiler-Lehman subtree kernel.RetGKII and RetGKII(MC) are also reported as faster than baseline methods, with practical running times.Source: §6.3 · p. 7

6.4 Sensitivity analysis

• RetGKII performs consistently across a wide range of random-walk step counts and feature-map dimensions on six benchmark datasets.The study varies S, D0, and Dc and measures average classification accuracy over ten repetitions of 10-fold cross-validation.Source: §6.4 · pp. 7–8, Figure 2 · p. 8

6.3 Experimental Results

• RetGKI and RetGKII are superior or comparable overall; on six named datasets, their accuracies exceed the best baselines by at least six percentage points.The six datasets are COLLAB, REDDIT-BINARY, REDDIT-MULTI(12K), Synthie, BZR, and COX2.Source: §6.3 · p. 7, Table 1 · p. 8, Table 2 · p. 8

• Return probability features characterize and compare the structural roles of nodes across graphs.Source: §7 · p. 8
• The features support RKHS graph embeddings for RetGKI, while approximate explicit feature maps yield tensor representations and computationally efficient RetGKII.Source: §7 · p. 8
• RetGKI and RetGKII achieve promising results on many benchmark datasets, with potential usefulness in many applications.Source: §7 · p. 8

• Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai are listed with Washington University in St. Louis’s Department of Electrical and Systems Engineering.Source: of Random Walks: Supplementary Material · p. 11

• Supplementary materials provide proofs of the mathematical results and detailed descriptions of the benchmark graph datasets.Source: Abstract · p. 11

1.1 Proving Proposition 1

• For isomorphic graphs, the proof uses a permutation matrix to relate their adjacency and degree matrices by conjugation.The resulting matrix identities are AH = ΠT AGΠ and DH = ΠT DGΠ.Source: §1.1 · p. 11

1.2 Proving Theorem 1

• For connected graphs of the same size and volume, matching return probabilities yields matching transition-matrix eigenvalue sets and corresponding eigenvector-component magnitudes under a permutation.The proof concludes that the absolute eigenvector components agree for the corresponding nodes and eigenvectors.Source: §1.2 · pp. 11, 14

1.3 Proving proposition 2

• Kernels formed from graph mean embeddings, including polynomial forms, are positive definite on the graph space.The proof invokes closure of positive-definite kernels under sums and products.Source: §1.3 · p. 14

1.4 Proving theorem 2

• Approximate explicit feature maps represent each graph embedding as a tensor, whose inner product converges to the exact embedding inner product as feature dimensions grow.The convergence holds as D0, D1, ..., DL → ∞.Source: §1.4 · p. 15

1.5 Proving proposition 3

• The approximate graph kernels are positive definite and converge to their corresponding exact kernels as feature dimensions grow.The proof derives both properties from Theorem 2.Source: §1.5 · p. 16

2 Datasets description

• The benchmark description organizes datasets by node-attribute regime, with statistics reported for the collection.The following subsections cover unlabeled graphs and graphs with discrete, continuous, or both kinds of attributes.Source: §2 · p. 16

2.1 Non-attributed (unlabeled) graph datasets

• Unlabeled benchmarks include social-network tasks such as classifying researcher collaboration networks and Reddit discussions.COLLAB labels researchers by scientific field; REDDIT-BINARY distinguishes question/answer from discussion communities.Source: §2.1 · p. 16

2.2 Graphs with discrete attributes

• Discrete-attribute datasets include protein graphs labeled by enzyme status and molecular graphs labeled by mutagenic effect.In DD, nodes are amino acids connected when less than six Angstroms apart; MUTAG graphs represent chemical compounds.Source: §2.2 · p. 17

2.3 Graphs with continuous attributes

• Continuous-attribute benchmarks include synthetic graphs with normally sampled node attributes and Synthie graphs with 15-dimensional attributes.SYNTHETIC uses N(0, 1) attributes; Synthie contains variants of two Erdos-Renyi graphs.Source: §2.3 · p. 17

2.4 Graphs with both discrete and continuous attributes

• Combined-attribute benchmarks include protein graphs with discrete SSE types and continuous lengths, plus chemical graphs with atom types and 3D coordinates.BZR, COX2, and DHFR are chemical compound datasets.Source: §2.4 · p. 17