A Property Testing Framework for the Theoretical Expressivity of Graph Kernels

1 Introduction

Linked data arises in various domains such as chem- and bioinformatics, social network analysis and pattern recognition. Such data can naturally be represented by graphs. Therefore, machine learning on graphs has become an active research area of increasing importance. The prevalent approach to classify graphs is to design kernels on graphs in order to employ standard kernel methods such as support vector machines. Consequently, in the past two decades a large number of graph kernels have been proposed, see, e.g., [Vishwanathan et al., 2010]. Most graph kernels decompose graphs and add up the pairwise similarities between their substructures following the seminal concept of convolution kernels [Haussler, 1999]. Here, substructures may be walks [G¨artner et al., 2003] or certain subgraphs [Ramon and G¨artner, 2003; Shervashidze et al., 2009]. Considering the large number of available graph kernels and the wealth of available benchmark data sets [Kersting et al., 2016], it becomes increasingly difficult to perform a fair experimental comparison of kernels and to assess their advantages and disadvantages for specific data sets. Indeed, current experimental comparisons cannot give a complete picture and are of limited help to a practitioner who has to choose a kernel for a particular application.

Graph kernels are developed with the (possibly conflicting) goals of being efficiently computable and capturing the topological information of the input graphs adequately. Newly proposed graph kernels are often justified by their ability to take structural graph properties into account that were ignored by previous kernels. Yet, to the best of our knowledge, this argument has not been formalized. Moreover, there is no theoretical justification why certain kernels perform better than others, but merely experimental evaluations. We address this by introducing a theoretical framework for the analysis of the expressivity of graph kernels motivated by concepts from property testing, see, e.g., [Goldreich, 2017]. We consider normalized kernels, which measure similarity in terms of angles in a feature space. We say that a graph kernel identifies a property if no two graphs are mapped to the same normalized feature vector unless they both have or both do not have the property. A positive angle between two such feature vectors can be helpful to classify the property. As the graph size increases, on the one hand, this angle can become very small (dependent on the graph size), which is hindering when applying this knowledge to a learning setting. On the other hand, we observe that a constant angle between any two feature vectors of two graphs with complementing properties can only rarely be the case, since only a marginal change in a graph's features can change its property. If a graph can be edited slightly to obtain a property, it can, however, be viewed as close enough to the property to be ignored. Thus, in the sense of property testing, it is desirable to differentiate between the graph set far away from a property and the property itself, which motivates the following concept. We say that a graph kernel distinguishes a property if it guarantees a constant angle (independent of the graph size) between the feature vectors of any two graphs, one of which has the property and the other is far away from doing so. We study well-known graph kernels and their ability to identify and distinguish fundamental properties such as connectivity.

The significance of our framework is demonstrated by addressing several current research questions. In the graph kernels literature it has been argued that many kernels take either local or global graph properties into account, but not both [Kondor and Pan, 2016; Morris et al., 2017]. Recent property testing results, however, suggest that under mild assumptions local graph features are sufficient to derive global properties [Newman and Sohler, 2013]. We consider a graph kernel based on local k-discs which can, in contrast to previous kernels, distinguish global properties such as planarity in bounded-degree graphs. For a constant dimensional feature space, we obtain learning guarantees for kernels that distinguish the class label property.

1.1 RelatedWork

We summarize related work on graph kernels, graph isomorphism, and property testing.

G¨artner et al. [2003] and Kashima et al. [2003] simultaneously proposed graph kernels based on random walks, which count the number of walks two graphs have in common. Since then, random walk kernels have been studied intensively, see, e.g., [Sugiyama and Borgwardt, 2015; Vishwanathan et al., 2010; Kriege et al., 2014]. Borgwardt and Kriegel [2005] have introduced kernels based on shortest paths; Costa and De Grave [2010] based on neighborhood subgraphs. Recently, graph kernels using matchings [Kriege et al., 2016] and geometric embeddings [Johansson and Dubhashi, 2015] have been proposed. Furthermore, spectral approaches were explored [Kondor and Pan, 2016]. A different line in the development of graph kernels focused on scalable graph kernels, see, e.g., [Shervashidze et al., 2011; Morris et al., 2016; Hido and Kashima, 2009].

There are few works which investigate graph kernels from a theoretical viewpoint. G¨artner et al. [2003] introduced the concept of a complete graph kernel as a graph kernel with an injective feature map. The concept of completeness is too strict for the comparison of graph kernels and none of the numerous graph kernels proposed for practical applications actually is complete. Two measures of expressivity of kernels from statistical learning theory where proposed and applied to graph kernels [Oneto et al., 2017] . However, these measures are not specific to graph structured data and cannot be interpreted in terms of distinguishable graph properties. The ability of the Weisfeiler-Lehman test to recognize non-isomorphic graphs has been studied extensively and the class of identifiable graphs characterized recently [Kiefer et al., 2015; Arvind et al., 2015].

Goldreich et al. [1998] formally established the study of property testing, where a central aim is to decide with high probability in sublinear time whether a property is satisfied or whether it is far from doing so. Goldreich and Ron [2002] initiated a growing line of research of property testers in the bounded degree graph model. For a recent overview, see, e.g., the textbook by Goldreich [2017].

1.2 Our Contribution

We propose a theoretical framework for comparing the expressiveness of kernels on bounded-degree graphs. Within this framework we obtain the following results:

• The shortest path kernel cannot guarantee a constant angle between connected and disconnected graphs of arbitrary size (see Proposition 3.2), but distinguishes connectivity in the considered framework (see Theorem 4.4).
• The random walk kernel and the Weisfeiler-Lehman subtree kernel both fail to identify connectivity, planarity, bipartiteness and triangle-freeness (see Theorems 4.1, 4.2).
• The graphlet kernel can identify triangle-freeness, but fails to distinguish any graph property (see Theorem 4.5).
• We define the k-disc kernel and show that it is able to distinguish connectivity, planarity, and triangle-freeness (see Theorem 5.4).
• We show that the prediction error of the 1-nearest neighbor classifier based on a kernel that distinguishes the class label property can be bounded (see Section 6).

2 Preliminaries

An (undirected) graph G is a pair (V,E) with a finite set of vertices V and a set of edges E ⊆ {{u, v} ⊆ V | u ̸= v}. We denote the set of vertices and the set of edges of G by V (G) and E(G), respectively. A walk in a graph G is a sequence of vertices such that for each pair of consecutive vertices there exists an edge in E(G). A path is a walk that contains each vertex at most once; a cycle is a walk that ends in the starting vertex. Moreover, N(v) denotes the neighborhood of v in V (G), i.e., N(v) = {u ∈ V (G) | {u, v} ∈ E(G)}. The k-disc of a vertex v in V (G) is the subgraph induced by all vertices u such that there exists a path of length at most k between u and v. We say that two graphs G and H are isomorphic if there exists an edge preserving bijection ϕ : V (G) → V (H), i.e., {u, v} in E(G) if and only if (ϕ(u), ϕ(v)) in E(H). The equivalence classes of the isomorphism relation are called isomorphism types. We denote the set of graphs on n vertices by Gn.

Let χ be a non-empty set and let κ: χ×χ → R be a function. Then, κ is a kernel on χ if there is a Hilbert space Hκ and a mapping φ: χ → Hκ such that κ(x, y) = 〈φ(x), φ(y)〉 for all x and y in χ, where 〈·, ·〉 denotes the inner product of Hκ. We call φ a feature map, and Hκ a feature space of the kernel κ. Let ˆκ be the cosine normalized version of a kernel κ and denote its normalized feature map by ˆ φ, i.e.,

The normalized kernel ˆκ(x, y) is equal to the cosine of the angle between φ(x) and φ(y) in the feature space. Let G be the set of all graphs, then a kernel κ: G × G → R is called graph kernel.

2.1 Definitions fromProperty Testing

In this paper we assume the bounded-degree graph model. A graph is of d-bounded degree if its maximum degree is at most d. In the following d is always independent of the number of vertices n.

Let G and H be two d-bounded degree graphs in Gn. The edit distance ∆(G, H) between G and H is the minimum number of edge modifications, i.e., adding or deleting edges, that has to be performed on G in order to obtain an isomorphic copy of H. A graph property is a set P of graphs that is closed under isomorphism. We denote the set of graphs in P on n vertices by Pn. Let Pn be a non-empty graph property. A d-bounded degree graph G with n vertices is ε-far from Pn in the bounded degree model if for all d-bounded degree graphs H in Pn we have ∆(G, H) > εdn for ε > 0. Otherwise, it is ϵ-close.

In this paper we study the following graph properties. A graph G = (V, E) is called connected if for every two vertices u, v ∈ V (G) there exists a path from u to v. A graph G is planar if there exists an embedding of G in the plane such that no edges cross, it is bipartite if V (G) can be partitioned into two sets V1 and V2 ⊂ V (G) such that for each edge {u, v}, u ∈ V1 and v ∈ V2 or vice versa. A graph is triangle-free if it does not contain a cycle with three vertices.

2.2 Graph Kernels

In the following we review four popular graph kernels. First, we describe the Weisfeiler-Lehman subtree kernel which is based on the well-known color refinement algorithm for isomorphism testing [Babai and Kucera, 1979; Cai et al., 1992], which can be described as follows: Let G and H be graphs, and let l be a label function V (G) ∪ V (H) → Σ, e.g., l(v) = |N(v)| for v in V (G) ∪ V (H). In each iteration i ≥ 0, the color refinement algorithm computes a new label function li : V (G) ∪ V (H) → Σ. In iteration 0 we set l0 = l. Now in iteration i > 0, we set li (v) = relabel((li-1 (v), sort({{li-1 (u) | u ∈ N(v)}}))), for v in V (G) ∪ V (H), where sort(S) returns a sorted sequence of the labels in the multiset S and relabel is a bijection that maps a sequence of labels to a new unique label in Σ, which has not been used in previous iterations. If G and H have an unequal number of vertices labeled σ in Σ, they are not isomorphic. The idea of the Weisfeiler-Lehman subtree kernel [Shervashidze et al., 2011] is to compute the above algorithm for h ≥ 0 iterations and after each iteration i compute a feature map φi (G) in R|Σi| for each graph G, where Σi ⊆ Σ denotes the image of li . Each component φi (G)σj counts the number of occurrences of vertices labeled with σj in Σi. The overall feature map φ(G) is defined as the concatenation of the feature maps of all h iterations, i.e.,

Then, the Weisfeiler-Lehman subtree kernel for h iterations is κhWL (G, H) = 〈φ(G), φ(H)〉.

Secondly, we describe the shortest path kernel [Borgwardt and Kriegel, 2005]. Let G be a graph with label function l : V (G) → Σ and let d: V (G) × V (G) → N denote the shortest path distance function. Then, the feature map φ of the shortest path kernel maps a graph to a feature vector, where each component is associated with a triple (a, b, p) ∈ Σ × Σ × N and counts the number of shortest paths in G with length p from a vertex with label a to a vertex with label b [Shervashidze et al., 2011]. The shortest path kernel is then defined as κSP(G, H) = 〈φ(G), φ(H)〉. In our case, φ simply maps a graph G to a vector that represents G's frequency of shortest path lengths, since we consider unlabeled, undirected graphs.

The graphlet kernel counts the induced subgraphs on k vertices, for k ∈ {3, 4, 5} [Shervashidze et al., 2009]. Note that these subgraphs can be disconnected. Let σ1, . . . , σN denote the isomorphism types of graphs on k vertices. For a graph G the kernel computes φ(G) = (φ(G)σ1 , . . . , φ(G)σN ), where the component φ(G)σi counts the subgraphs of G of type σi. The kernel is computed by κkGR(G,H) = 〈φ(G), φ(H)〉 for two graphs G and H and graphlet size k.

Finally, the random walk kernel counts the number of common walks of two graphs. The kernel is defined via the direct product graph G × H of two graphs G and H as

with vertex set V× and adjacency matrix A× of G × H, k > 0, λ0, . . . , λk > 0, and A0× = I. For k = ∞ and λi = γ i , i ∈ N, and γ sufficiently small such that (2) converges, the kernel can be computed by a closed form expression and is referred to as geometric random walk kernel [G¨artner et al., 2003].

3 Distinguishable Graph Properties

Let n ∈ N be an arbitrary number of vertices. We say that a feature map φ can identify a graph G ∈ Gn (up to isomorphism) if for each other graph H ∈ Gn that is not isomorphic to G it holds that ˆ φ(G) ̸= ˆ φ(H).

Definition 3.1. Let P be a graph property. If a graph kernel κ : G ×G → R≥0 and for each n ∈ N, every G ∈ Pn and H /∈ Pn satisfy ˆκ(G, H) < 1, we say that P can be identified by κ.

In order for a graph kernel to be able to distinguish a graph property and to use this knowledge in a learning context, a desirable goal is to have a constant angle independent of n. In the strict sense this is, however, rarely the case. In fact, in the following instance a constant difference cannot be achieved.

Proposition 3.2. For the shortest path kernel, it holds that for each constant c, 0 < c < 1, there exist some n ∈ N and two graphs G, H ∈ Gn with G connected, and H not connected such that ˆκSP(G, H) > 1 - c.

Proof. Let, for each n ∈ N, G be a path with n vertices, and let H consist of a path with n - 1 vertices and one isolated vertex. Note that H is not connected, whereas adding one edge to H is enough to transform it into a connected graph which is isomorphic to G. The feature vectors for G and H counting the number of vertex pairs with distances 1 to n - 1 are φ = (n - 1, n - 2, . . . , 1) ∈ Rn-1 and ψ = (n - 2, n - 3, . . . , 1, 0) ∈ Rn-1 , respectively. Additionally, in H there are n - 1 vertex pairs that are not connected. It can be computed that 〈ˆ φ, ˆ ψ〉2 = 1- 3 4n2-8n+3 . Assume there is a constant c, 0 < c < 1, such that, for each n ∈ N, it holds that 〈ˆ φ, ˆ ψ〉 ≤ 1 - c, then there would be a constant c′ = (1 - c)2 , 0 < c′ < 1 such that c′ ≥ 1- 3 4n2-8n+3 which does not hold for a large choice of n. Thus, for each constant c there exists an n ∈ N such that, for the graphs G and H as chosen above, ˆκ(G, H) > 1 - c holds.

Note that both graphs in the proof of Proposition 3.2 have a maximum degree of 2. Therefore, the statements holds if any degree bound d ≥ 2 is required.

In order to be able to achieve an angle independent of the graph size, we suggest to employ the notion of a graph being ε-far from a property as used in property testing. We aim to obtain a constant 1 angle between the feature vectors of two graphs whenever one graph has a certain property and the other is ε-far from having that property. In this context we define distinguishability of a graph property by a graph kernel as follows. Note that distinguishablity implies identifiability.

Definition 3.3. In the bounded-degree graph model, a graph property P is called distinguishable by a graph kernel κ : G × G → R≥0, if for every ε > 0, d ∈ N, there exists some δ = δ(ε, d) > 0 such that for every n ∈ N, every G ∈ Pn, and every graph H that is ε-far from Pn, we have ˆκ(G, H) ≤ 1 - δ.

Note that this notion does not guarantee an accurate learning algorithm in general. Consider the isomorphism kernel that is 1 for two isomorphic graphs and 0 otherwise. It distinguishes every property, but as a classifier will not generalize to unseen data. Nevertheless, we obtain some learning guarantees, see Section 6.

1 By constant we refer to a value independent of the input size n, which, however, can depend on ε or d.

4 Properties Distinguishable by Popular Graph Kernels

In this section we study the identifiability and distinguishability of the random walk, the Weisfeiler-Lehman subtree, the shortest path, and the graphlet kernel. Table 1 sums up these results in comparison to the k-disc kernel studied in Section 5.

Both, the feature maps of a random walk kernel and the Weisfeiler-Lehman subtree kernel cannot identify a regular graph. In fact, each regular graph in Gn for some n ∈ N, maps to the same feature vector. In particular, for the random walk kernel, the number of walks of length ℓ starting in a vertex of a regular graph with degree d is dℓ . Hence, for two regular graphs with degrees d and d′ , respectively, it holds that κkRW(G,H) = |V×| ∑kℓ=0 λℓ(d · d′ )ℓ , independently from the adjacency matrix of the product graph. For the Weisfeiler-Lehman subtree kernel, two regular graphs with the same degree obtain the same feature vector due to [Arvind et al., 2015]. Therefore, as soon as for some graph property P and n ∈ N there exists one regular graph in Pn and another regular graph in Gn ∖Pn, both kernels cannot identify and, thus, not distinguish the graph property.

Theorem 4.1. The random walk kernel cannot identify connectivity, planarity, bipartiteness, or triangle freeness.

Proof. A cycle with six vertices and two triangles with three vertices, both regular graphs, are a counterexample to the distinguishability of connectivity. Furthermore, consider the graphs G and H as illustrated in Figure 1. Note that G is planar, but not bipartite, and contains triangles, whereas H is not planar, but bipartite, and triangle-free.

By the same arguments we obtain the following.

Theorem 4.2. The Weisfeiler-Lehman subtree kernel cannot identify connectivity, planarity, bipartiteness, or triangle freeness.

Next, we attend to a positive result regarding connectivity and the shortest path kernel. We will make use of the following technical lemma throughout proofs in this paper.

Lemma 4.3. Let n, r ∈ N, x ∈ Rr≥0 , and ε > 0. For a nonempty subset of indices S ⊆ {1, . . . , r} such that ∑i∈S |xi| = η > 0 the following holds for every y ∈ Rr≥0 with yi = 0 for

Proof. Without loss of generality, let S = {1, . . . , s}. For each y ∈ Rr≥0 with yi = 0, 1 ≤ i ≤ s, it holds that

which, by the Cauchy-Schwarz inequality is at most

Moreover, since ∑si=1 x2i ≥ 1s · (∑si=1 xi)2 = 1s η2 , this is at most √1 - η2/s‖x‖22 .

Theorem 4.4. The shortest path kernel

1. cannot identify planarity, bipartiteness, or triangle freeness;
2. can distinguish connectivity.

Proof. 1. While in general two regular graphs may have different feature vectors, the graphs in Figure 1 also serve as a counterexample here. In both cases the shortest path feature vector are equal, as there are nine shortest paths of length 1 and six of length 2, each.

1. Let n, d ∈ N, ε > 0, and H ∈ Gn be ε-far from being connected. For the shortest path feature vector ψ = (ψ1, . . . , ψn-1) and each connected graph G ∈ Gn with shortest path feature vector φ = (φ1, . . . , φn-1), it holds that 〈(ψ1, . . . , ψn-1), (φ1, . . . , φn-1)〉 = 〈(ψ1, . . . , ψn-1, η), (φ1, . . . , φn-1, 0)〉, where η denotes the number of disconnected vertex pairs in H. By Lemma 4.3 it holds that

Assume that n > 4/εd. Otherwise with η ≥ 1 and ‖ψ‖2 ≤ n2 ≤ (4/εd)2 , it holds that (3) is at most 1 minus a constant. Now, it is known that there are more than εdn/2 connected components of which at least εdn/4 have a size smaller than 4/εd [Goldreich and Ron, 2002]. At least one vertex in such a small component is disconnected from each vertex outside the component, that is, η is at least 1/2 · εdn/4 · (n-4/εd) = εn2 d/8 - n/2. Moreover, with 〈ψ, ψ〉 ≤ (n(n-1)/2 - η)2 + η2 we obtain that 1 - η2/‖ψ‖22 ≤ 1/2+ζ, for some ζ > 0 independent of n, which implies that (3) is smaller than 1 by a constant strictly between 0 and 1.

Finally, we consider the graphlet kernel κkGR. Although graphlet kernels appear to be rather expressive, from the considered properties they can only identify triangle-freeness. We can find counterexamples for connectivity, bipartiteness and planarity. For distinguishability there is one general obstacle, namely the fact that graphlets do not have to be connected. Each graph with n vertices and bounded degree d has at least 1 - d(k-1)k/2(n-1) k-graphlets with k independent vertices. Thus, for each constant δ > 0 and each G, H ∈ Gn it holds that ˆκkGR(G, H) > 1 - δ. Therefore, we obtain the following.

Theorem4.5. The graphlet kernel can identify triangle-freeness for k ≥ 3, but unless the graphlet size k depends on the graph size, it cannot identify connectivity, bipartiteness, or planarity. Moreover, the graphlet kernel cannot distinguish any graph property.

5 Graph Kernels that Distinguish Graph Properties

While we have observed that established graph kernels often cannot distinguish basic properties, we aim to find a graph kernel that can distinguish fundamental properties and is efficiently computable. Based on ideas by Costa and De Grave [2010] and Newman and Sohler [2013], we define a histogram histG(k) of the numbers of different k-discs, and the frequency vector freqG(k) = histG(k)/n of G ∈ Gn. Consider the following graph kernel.

Definition 5.1. Given two graphs G and H, the k-disc graph kernel is defined by κKD(G, H) = 〈freqG(k), freqH(k)〉.

A significant difference between the k-disc kernel and the graphlet kernel is that a k-disc is a connected subgraph, while a graphlet may be disconnected. For d-bounded-degree graphs, the k-disc kernel can be computed in time linear in the graph size. It can even be approximated in constant time, see, e.g., [Newman and Sohler, 2013].

Theorem 5.4 comprises the main results of this section about graph properties distinguishable by the k-disc kernel. From property testing studies, see, e.g., [Newman and Sohler, 2013], we often obtain information about the 1-norm of the distance between the frequency vectors of a graph ε-far from a property and all graphs satisfying the property. In order to translate these facts to a positive angle between the frequency vectors, we need the following two lemmas. Firstly, it can be seen that for two normalized real vectors with at least one index at which the entries differ by at least a constant positive value, their (standard) inner product is strictly less than 1.

Lemma 5.2. Let x, y be two vectors in Rn≥0 for some n ∈ N with ‖x‖2 = ‖y‖2 = 1. Let ζ > 0 be an arbitrarily small real value. If there exists some i, 1 ≤ i ≤ n such that |xi - yi| ≥ ζ, then 〈x, y〉 ≤ 1 - ζ 2/2.

Thus, the angle between x and y is positive and constant.

Secondly, we need to take care of the fact that the studied frequency vectors are normalized with respect to their 1-norm. However, since the number of different k-discs is independent of the number of vertices in the bounded-degree model, we can show the following lemma for two frequency vectors with a positive distance with respect to their 1-norm.

Lemma 5.3. Let φ and ψ be two vectors in Rn≥0 with ‖φ‖1 = ‖ψ‖1 =1 and ‖φ - ψ‖1 ≥ η. Then, there exists an index i, 1 ≤ i ≤ n, and a real value ζ > 0 such that |φi/‖φ‖2 - ψi/‖ψ‖2 |≥ζ.

Proof. Let wlog ‖φ‖2 ≥ ‖ψ‖2 . Moreover, let s denote the number of positive entries in both, φ and ψ. ‖φ-ψ‖1 ≥ η implies the existence of a j: φj - ψj ≥ ηs . Case 1: If ‖φ‖2 -

Case 2: ‖φ‖2-‖ψ‖2 > η 2s3/2 . Let R denote the subset of indices i such that φi/‖φ‖2 > ψi/‖ψ‖2 . Observe, that 0 ≤ |R| < s. We split the sum ‖ˆ φ - ˆ ψ‖1 = ∑ni=1 |φi/‖φ‖2 - ψi/‖ψ‖2 | up into indices i ∈ R and i /∈ R. Since ‖ψ‖1 = ‖φ‖1 = 1, this is equal to

Thus, there exists an index i, 1 ≤ i ≤ n, such that |φi/‖φ‖2 - ψi/‖ψ‖2 | > η/2s5/2 . With 0 < ζ ≤ η/2s5/2 in both cases, this completes the proof.

Finally, we can proof the main theorem of this section.

Theorem 5.4. For the k-disc graph kernel, it holds that

1. connectivity is distinguishable for k ≥ 4/εd,
2. triangle-freeness for k ≥ 1, and
3. for each ε > 0, d ∈ N there exists some k ∈ N+ such that distinguishability is satisfied for planarity.

Proof. 1. Let H ∈ Gn be a graph with bounded degree d that is ε-far from being connected for some ε > 0. By [Goldreich and Ron, 2002] we know that the number of connected components of a size smaller than 4/εd is at least εdn/4. For each vertex in such a small component, the full component is found as a k-disc of size 4/εd in H. For each connected graph G, the frequency of such a small component is 0, since each k-disc covers at least 4/εd vertices. Therefore, ‖freqG(k) - freqH(k)‖1 ≥ εd/4. The conditions of Lemma 4.3 are satisfied for x = freqH(k) and y = freqG(k) with S indicating the occurrence of small components. Again, observe that |S| is independent of n. By ‖x‖22 ≤ 1 and η ≥ εd 4 we obtain 〈x,y〉/‖x‖2 ‖y‖2 ≤ √1 - εd/4|S|, which is a positive constant strictly less than 1.

1. For triangle-freeness, again, we can use similar arguments to [Goldreich and Ron, 2002]. If a graph is ε-far from being triangle-free, there are εdn superfluous edges in H in contrast to any triangle-free graph G. Note that only edges that are part of a triangle are to be removed. Each such edge is shared by two vertices, and there can be at most d edges involved per vertex. That means, that at least 2εn vertices are incident to a superfluous edge. These vertices hence have k-discs, for each k ≥ 1, that contain triangles, whereas in G there are no such k-discs. Therefore, ‖freqG(k) - freqH(k)‖1 ≥ 2ε. Since the frequency vectors are always normalised with respect to their 1-norm, the conditions of Lemma 5.3 hold. Thus, there exists an index i, 1 ≤ i ≤ n, and a constant ζ > 0 such that ∣∣∣ freqG(k)i ‖freqG(k)‖2 - freqG(k)i ‖freqH (k)‖2 ∣∣∣ ≥ ζ. Then, by Lemma 5.2, 〈 freqG(k)i ‖freqG(k)‖2 , freqG(k)i ‖freqH (k)‖2 〉 is smaller than 1 by a constant.
2. Benjamini et al. [2010] show that for each ε > 0 and degree bound d, there exists a positive integer k independent of n such that for any two graphs G, H ∈ Gn with bounded degree d, G planar, H ε-far from being planar, it holds that ‖freqG(k)-freqH(k)‖ ≥ 1/k. Therefore, via Lemmas 5.3 and 5.2, we obtain the claimed result.

6 A Learning Algorithm

In this section we study a kernel nearest neighbor classifier for graphs and show that its prediction error can be bounded under the assumption that the employed kernel can distinguish the class label property and that all considered graphs either satisfy the property or are ϵ-far from it. We assume the following supervised binary classification problem: Let Y = {0, 1} be the set of possible class labels, which represent if a graph has a property or not. We aim to learn a concept c : Gn → Y such that the 0-1 loss is minimized. Thereto we receive a training set {g1, . . . , gm} ⊂ Gn and a test graph from Gn sampled i.i.d. according to some unknown distribution, as well as the set of class labels {c(g1), . . . , c(gn)} for the training set based on the concept to be learned. We assume in the following that for the considered graph property, Gn only contains graphs that either have the property or are ϵ-far from it.

6.1 Kernel Nearest Neighbor Classification

Based on a training set T of data points in RD with known class labels, the k-nearest neighbor classifier (k-NN) assigns a test data point to the class most common among its k nearest neighbors in T . Here, the nearest neighbors are commonly determined based on the Euclidean distance between data points. Kernel nearest neighbor classifiers have been realized by substituting this distance by a kernel metric in Hilbert space, see, e.g., [Yu et al., 2002]. For a kernel κ with feature map φ, we consider the 1-NN algorithm using the kernel metric dκ(x, y) = ‖φ(x) - φ(y)‖2 = √κ(x, x) + κ(y, y) - 2κ(x, y).

6.2 LearningWith Distinguishing Kernels

We again consider the cosine normalized version ˆκ of a kernel κ and its normalized feature map ˆ φ. For dimension D of the feature space, the normalized feature map ˆ φ assigns graphs to points on the unit sphere SD-1 . Let us assume that ˆκ distinguishes the class label property. Then, there is a δ, such that for all graphs G that have the property and H that are ε-far from it, we have ˆκ(G,H) ≤ 1 - δ and, consequently, dˆκ(G, H) ≥ √1 + 1 - 2(1 - δ) = √2δ. We denote this guaranteed minimum distance by ∆ = √2δ. Consider the spherical cap C within the open ball centered at ˆ φ(G) with radius ∆. According to the assumption, every graph H with ˆ φ(H) lying on C, must have the same class label.

Proposition 6.1. Let G be a graph of the training set. Then every graph H with dˆκ(G, H) < ∆ is correctly classified by 1-NN where the base set contains all graphs that either have the property or are ε-far from it.

Proof. Assume H is not correctly classified and dˆκ(G, H) < ∆. Due to distinguishability, H must belong to the same class as G. Since H is not correctly classified by 1-NN, there must be a nearest neighbor N ̸= G of H with a different class label. Since N is a nearest neighbor of G, we have dˆκ(H,N) ≤ dˆκ(G, H) < ∆, contradicting distinguishability.

We say that an algorithm (ε, λ)-learns a property if a test graph G drawn from the underlying distribution is correctly classified with probability (1 - λ) and the base set consists of all graphs that either have the property or are ϵ-far from it.

Theorem 6.2. Let κ be a kernel that distinguishes the class label property according to Definition 3.3 with some fixed δ and a feature space of dimension D. Let ∆ = √2δ. Let all graphs either satisfy the property or be ϵ-far from it. Assume that the training set has cardinality m ≥ (1+6/∆)D/λ ln((1+6/∆)D/λ) then the 1-NN algorithm (ε, λ)-learns the property.

Proof (Sketch). We cover the unit sphere with balls of radius ∆/3. It is well-known that such a cover of size B = (1+6/∆)D exists. We observe that if a training example falls into a ball of the cover then by Proposition 6.1 any other example inside this ball is correctly classified. We observe that with probability 1 - λ every ball with probability mass at least λ/B contains a training example. The overall probability of the remaining balls is at most λ. Therefore, with probability 1 - λ the algorithm (ϵ, λ)-learns the property.

7 Conclusion

The introduced framework provides a starting point, e.g., for investigating other properties and evaluating other graph kernels. We assume promising kernels to be based, e.g., on other property testers, on spectral information, or on the 3-dimensional Weisfeiler-Lehman test. So far we have considered unlabeled, undirected graphs. Since most popular graph kernels are designed for labeled graphs, e.g., nodes are annotated with chemical symbols, future work might consider these as well.

Acknowledgements

This research was supported by the German Science Foundation (DFG) within the Collaborative Research Center SFB 876 "Providing Information by Resource-Constrained Data Analysis", project A6 "Resource-efficient Graph Mining".