nips nips2009 nips2009-95 knowledge-graph by maker-knowledge-mining

95 nips-2009-Fast subtree kernels on graphs

Source: pdf

Author: Nino Shervashidze, Karsten M. Borgwardt

Abstract: In this article, we propose fast subtree kernels on graphs. On graphs with n nodes and m edges and maximum degree d, these kernels comparing subtrees of height h can be computed in O(mh), whereas the classic subtree kernel by Ramon & G¨ rtner scales as O(n2 4d h). Key to this efﬁciency is the observation that the a Weisfeiler-Lehman test of isomorphism from graph theory elegantly computes a subtree kernel as a byproduct. Our fast subtree kernels can deal with labeled graphs, scale up easily to large graphs and outperform state-of-the-art graph kernels on several classiﬁcation benchmark datasets in terms of accuracy and runtime. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Fast subtree kernels on graphs Nino Shervashidze, Karsten M. [sent-1, score-0.836]

2 de Abstract In this article, we propose fast subtree kernels on graphs. [sent-6, score-0.623]

3 On graphs with n nodes and m edges and maximum degree d, these kernels comparing subtrees of height h can be computed in O(mh), whereas the classic subtree kernel by Ramon & G¨ rtner scales as O(n2 4d h). [sent-7, score-1.695]

4 Key to this efﬁciency is the observation that the a Weisfeiler-Lehman test of isomorphism from graph theory elegantly computes a subtree kernel as a byproduct. [sent-8, score-0.889]

5 Our fast subtree kernels can deal with labeled graphs, scale up easily to large graphs and outperform state-of-the-art graph kernels on several classiﬁcation benchmark datasets in terms of accuracy and runtime. [sent-9, score-1.379]

6 1 Introduction Graph kernels have recently evolved into a branch of kernel machines that reaches deep into graph mining. [sent-10, score-0.614]

7 Several different graph kernels have been deﬁned in machine learning which can be categorized into three classes: graph kernels based on walks [5, 7] and paths [2], graph kernels based on limited-size subgraphs [6, 11], and graph kernels based on subtree patterns [9, 10]. [sent-11, score-1.938]

8 While fast computation techniques have been developed for graph kernels based on walks [12] and on limited-size subgraphs [11], it is unclear how to compute subtree kernels efﬁciently. [sent-12, score-1.076]

9 As a consequence, they have been applied to relatively small graphs representing chemical compounds [9] or handwritten digits [1], with approximately twenty nodes on average. [sent-13, score-0.459]

10 But could one speed up subtree kernels to make them usable on graphs with hundreds of nodes, as they arise in protein structure models or in program ﬂow graphs? [sent-14, score-0.898]

11 It is a general limitation of graph kernels that they scale poorly to large, labeled graphs with more than 100 nodes. [sent-15, score-0.648]

12 While the efﬁcient kernel computation strategies from [11, 12] are able to compare unlabeled graphs efﬁciently, the efﬁcient comparison of large, labeled graphs remains an unsolved challenge. [sent-16, score-0.813]

13 Could one speed up subtree kernels to make them the kernel of choice for comparing large, labeled graphs? [sent-17, score-0.896]

14 The goal of this article is to address both of the aforementioned questions, that is, to develop a fast subtree kernel that scales up to large, labeled graphs. [sent-18, score-0.794]

15 In Section 2, we review the subtree kernel from the literature and its runtime complexity. [sent-20, score-0.982]

16 In Section 3, we describe an alternative subtree kernel and its efﬁcient computation based on the Weisfeiler-Lehman test of isomorphism. [sent-21, score-0.686]

17 In Section 4, we compare these two subtree kernels to each other, as well as to a set of four other state-of-the-art graph kernels and report results on kernel computation runtime and classiﬁcation accuracy on graph benchmark datasets. [sent-22, score-1.787]

18 1 2 The Ramon-G¨ rtner subtree kernel a Terminology We deﬁne a graph G as a triplet (V, E, L), where V is the set of vertices, E the set of undirected edges, and L : V → Σ a function that assigns labels from an alphabet Σ to nodes in the graph1 . [sent-23, score-1.229]

19 For simplicity, we assume that every graph has n nodes, m edges, a maximum degree of d, and that there are N graphs in our given set of graphs. [sent-25, score-0.414]

20 A walk is a sequence of nodes in a graph, in which consecutive nodes are connected by an edge. [sent-26, score-0.406]

21 A (rooted) subtree is a subgraph of a graph, which has no cycles, but a designated root node. [sent-28, score-0.406]

22 A subtree of G can thus be seen as a connected subset of distinct nodes of G with an underlying tree structure. [sent-29, score-0.596]

23 The height of a subtree is the maximum distance between the root and any other node in the graph plus one. [sent-30, score-0.718]

24 Similarly, the notion of subtrees can be extended to subtree patterns (also called ‘tree-walks’ [1]), which can have nodes that are equal. [sent-32, score-0.636]

25 Note that all subtree kernels compare subtree patterns in two graphs, not (strict) subtrees. [sent-34, score-1.028]

26 Let S(G) refer to the set of all subtree patterns in graph G. [sent-35, score-0.606]

27 Deﬁnition The ﬁrst subtree kernel on graphs was deﬁned by [10]. [sent-36, score-0.905]

28 Complexity The runtime complexity of the subtree kernel for a pair of graphs is O(n2 h4d ), including a comparison of all pairs of nodes (n2 ), and a pairwise comparison of all matchings in their neighbourhoods in O(4d ), which is repeated in h iterations. [sent-39, score-1.549]

29 h is a multiplicative factor, not an exponent, as one can implement the subtree kernel recursively, starting with k1 and recursively computing kh from kh−1 . [sent-40, score-0.744]

30 For a dataset of N graphs, the resulting runtime complexity is then obviously in O(N 2 n2 h4d ). [sent-41, score-0.351]

31 Related work The subtree kernels in [9] and [1] reﬁne the above deﬁnition for applications in chemoinformatics and hand-written digit recognition. [sent-42, score-0.593]

32 Mah´ and Vert [9] deﬁne extensions of the e classic subtree kernel that avoid tottering [8] and consider unbalanced subtrees. [sent-43, score-0.686]

33 This restricts the set of matchings to matchings of up to α nodes, but the runtime complexity is still exponential in this parameter α, which both papers describe as feasible on small graphs (with approximately 20 nodes) with many distinct node labels. [sent-45, score-0.751]

34 We present a subtree kernel that is efﬁcient to compute on graphs with hundreds and thousands of nodes next. [sent-46, score-1.047]

35 1 Fast subtree kernels The Weisfeiler-Lehman test of isomorphism Our algorithm for computing a fast subtree kernel builds upon the Weisfeiler-Lehman test of isomorphism [14], more speciﬁcally its 1-dimensional variant, also known as “naive vertex reﬁnement”, which we describe in the following. [sent-49, score-1.397]

36 2: Sorting each multiset • Sort elements in Mh (v) in ascending order and concatenate them into a string sh (v). [sent-53, score-0.607]

37 3: Sorting the set of multisets • Sort all of the strings sh (v) for all v from G and G in ascending order. [sent-55, score-0.514]

38 4: Label compression • Map each string sh (v) to a new compressed label, using a function f : Σ∗ → Σ such that f (sh (v)) = f (sh (w)) if and only if sh (v) = sh (w). [sent-56, score-0.934]

39 The sorting step 3 allows for a straightforward deﬁnition and implementation of f for the compression step 4: one keeps a counter variable for f that records the number of distinct strings that f has compressed before. [sent-58, score-0.366]

40 f assigns the current value of this counter to a string if an identical string has been compressed before, but when one encounters a new string, one increments the counter by one and f assigns its value to the new string. [sent-59, score-0.383]

41 Complexity The runtime complexity of Weisfeiler-Lehman algorithm with h iterations is O(hm). [sent-64, score-0.343]

42 For a ﬁxed h, the cardinality of this set is upper-bounded by n, which means that we can sort all multisets in O(m) by the following procedure: We assign the elements of all multisets to their corresponding buckets, recording which multiset they came from. [sent-69, score-0.458]

43 The runtime is O(m) as there are O(m) elements in the multisets of a graph in iteration h. [sent-71, score-0.595]

44 2 The Weisfeiler-Lehman kernel on pairs of graphs Based on the Weisfeiler-Lehman algorithm, we deﬁne the following kernel function. [sent-76, score-0.755]

45 3 Deﬁnition 1 The Weisfeiler-Lehman kernel on two graphs G and G is deﬁned as: (h) kW L (G, G ) = |{(si (v), si (v ))|f (si (v)) = f (si (v )), i ∈ {1, . [sent-77, score-0.596]

46 That is, the Weisfeiler-Lehman kernel counts common multiset strings in two graphs. [sent-81, score-0.609]

47 (h) Proof Intuitively, kW L is a kernel because it counts matching subtree patterns of up to height h in two graphs. [sent-83, score-0.833]

48 (h) As f (s) = s and hence each string s corresponds to exactly one subtree pattern t, kW L deﬁnes a (h) kernel with corresponding feature map φW L , such that (h) (h) φW L (G) = (φ(h) (G))s∈Σ∗ = (φt (G))t∈S(G) . [sent-96, score-0.761]

49 s (7) Theorem 3 The Weisfeiler-Lehman kernel on a pair of graphs G and G can be computed in O(hm). [sent-97, score-0.499]

50 Proof This follows directly from the deﬁnition of the Weisfeiler-Lehman kernel and the runtime complexity of the Weisfeiler-Lehman test, as described in Section 3. [sent-98, score-0.576]

51 3 The Weisfeiler-Lehman kernel on N graphs For computing the Weisfeiler-Lehman kernel on N graphs we propose the following algorithm which improves over the naive, N 2 -fold application of the kernel from (4). [sent-102, score-1.254]

52 We now process all N graphs simultaneously and conduct the steps given in the Algorithm 2 in each of h iterations on each graph G. [sent-103, score-0.437]

53 The hash function g can be implemented efﬁciently: it again keeps a counter variable x which counts the number of distinct strings that g has mapped to compressed labels so far. [sent-104, score-0.394]

54 Theorem 4 For N graphs, the Weisfeiler-Lehman kernel on all pairs of these graphs can be computed in O(N hm + N 2 hn). [sent-107, score-0.58]

55 Proof Naive application of the kernel from deﬁnition (4) for computing an N × N kernel matrix would require a runtime of O(N 2 hm). [sent-108, score-0.832]

56 This can be achieved by replacing the compression mapping f in the classic Weisfeiler-Lehman algorithm by a hash function g that is applied to all N graphs simultaneously. [sent-110, score-0.353]

57 4 Algorithm 2 One iteration of the Weisfeiler-Lehman kernel on N graphs 1: Multiset-label determination • Assign a multiset-label Mh (v) to each node v in G which consists of the multiset {lh−1 (u)|u ∈ N (v)}. [sent-111, score-0.766]

58 2: Sorting each multiset • Sort elements in Mh (v) in ascending order and concatenate them into a string sh (v). [sent-112, score-0.607]

59 3: Label compression • Map each string sh (v) to a compressed label using a hash function g : Σ∗ → Σ such that g(sh (v)) = g(sh (w)) if and only if sh (v) = sh (w). [sent-114, score-1.002]

60 To get all pairwise kernel values we have to multiply all feature vectors, which requires a (h) runtime of O(N 2 hn), as each graph G has at most hn non-zero entries in φW L (G). [sent-122, score-0.837]

61 4 Link to the Ramon-G¨ rtner kernel a The Weisfeiler-Lehman kernel can be deﬁned in a recursive fashion which elucidates its relation to the Ramon-G¨ rtner kernel. [sent-124, score-0.968]

62 1 10 1 2 10 0 3 10 Number of graphs N 10 15 10 5 0 200 400 600 Graph size n 800 1000 20 Runtime in seconds Runtime in seconds 20 0 2 3 4 5 6 Subtree height h 7 15 10 5 0 0. [sent-131, score-0.412]

63 9 Figure 1: Runtime in seconds for kernel matrix computation on synthetic graphs using the pairwise (red, dashed) and the global (green) Weisfeiler-Lehman kernel (Default values: dataset size N = 10, graph size n = 100, subtree height h = 5, graph density c = 0. [sent-140, score-1.809]

64 Theorem 5 highlights the following differences between the Weisfeiler-Lehman and the RamonG¨ rtner kernel: In (8), Weisfeiler-Lehman considers all subtrees up to height h and the Ramona G¨ rtner kernel the subtrees of exactly height h. [sent-143, score-1.028]

65 In (9) and (10), the Weisfeiler-Lehman kernel checks a whether the neighbourhoods of v and v match exactly, whereas the Ramon-G¨ rtner kernel considers a all pairs of matching subsets of the neighbourhoods of v and v in (3). [sent-144, score-0.878]

66 In our experiments, we next examine the empirical differences between these two kernels in terms of runtime and prediction accuracy on classiﬁcation benchmark datasets. [sent-145, score-0.572]

67 1 Experiments Runtime behaviour of Weisfeiler-Lehman kernel Methods We empirically compared the runtime behaviour of our two variants of the WeisfeilerLehman (WL) kernel. [sent-147, score-0.626]

68 The ﬁrst variant computes kernel values pairwise in O(N 2 hm). [sent-148, score-0.333]

69 The second variant computes the kernel values in O(N hm + N 2 hn) on the dataset simultaneously. [sent-149, score-0.393]

70 Experimental setup We assessed the behaviour on randomly generated graphs with respect to four parameters: dataset size N , graph size n, subtree height h and graph density c. [sent-151, score-1.171]

71 The density of an undirected graph of n nodes without self-loops is deﬁned as the number of its edges divided by n(n − 1)/2, the maximal number of edges. [sent-152, score-0.367]

72 We then computed the pairwise and the global 6 WL kernel on these synthetic graphs. [sent-164, score-0.348]

73 Results Empirically, we observe that the pairwise kernel scales quadratically with dataset size N . [sent-167, score-0.361]

74 The N 2 sparse vector multiplications that have to be performed for kernel computation with global WL do not dominate runtime here. [sent-169, score-0.64]

75 When varying the number of nodes n per graph, we observe that the runtime of global WL scales linearly with n, and is much faster than the pairwise WL for large graphs. [sent-171, score-0.576]

76 We observe the same picture for the height h of the subtree patterns. [sent-172, score-0.505]

77 The runtime of both kernels grows linearly with h, but the global WL is more efﬁcient in terms of runtime in seconds. [sent-173, score-0.867]

78 Varying the graph density c, both methods show again a linearly increasing runtime, although the runtime of the global WL kernel is close to constant. [sent-174, score-0.812]

79 The density c seems to be a graph property that affects the runtime of the pairwise kernel more severely than that of global WL. [sent-175, score-0.864]

80 Across all different graph properties, the global WL kernel from Section 3. [sent-176, score-0.467]

81 3 requires less runtime than the pairwise WL kernel from Section 3. [sent-177, score-0.628]

82 Hence the global WL kernel is the variant of our Weisfeiler-Lehman kernel that we use in the following graph classiﬁcation tasks. [sent-179, score-0.748]

83 Each protein is represented by a graph, in which the nodes are amino acids and two nodes are connected by an edge if they are less than 6 Angstroms apart. [sent-189, score-0.395]

84 , 10−6 } by cross-validation on the training set), the graphlet kernel from [11] that counts common induced labeled connected subgraphs of size 3, and the shortest path kernel from [2] that counts pairs of labeled nodes with identical shortest path distance. [sent-194, score-1.257]

85 We report the total runtime of this computation (not the average per kernel matrix). [sent-203, score-0.6]

86 Results In terms of runtime the Weisfeiler-Lehman kernel can easily scale up even to graphs with thousands of nodes. [sent-204, score-0.819]

87 The shortest path kernel is competitive to the WL kernel on smaller graphs (MUTAG, NCI1, NCI109), but on D&D; its runtime degenerates to more than 23 hours. [sent-206, score-1.199]

88 The Ramon and G¨ rtner kernel was computable a on MUTAG in approximately 40 minutes, but for the large NCI datasets it only ﬁnished computation on a subsample of 100 graphs within two days. [sent-207, score-0.819]

89 The random walk kernel is competitive on MUTAG, but as the RamonG¨ rtner kernel, does not ﬁnish computation on the full NCI datasets and on D&D; within two days. [sent-209, score-0.675]

90 a The graphlet kernel is faster than our WL kernel on MUTAG and the NCI datasets, and about a 7 Method/Dataset Weisfeiler-Lehman a Ramon & G¨ rtner Graphlet count Random walk Shortest path MUTAG 82. [sent-210, score-1.02]

91 Table 1: Prediction accuracy (± standard error) on graph classiﬁcation benchmark datasets Dataset Maximum # nodes Average # nodes # labels Number of graphs Weisfeiler-Lehman Ramon & G¨ rtner a Graphlet count Random walk Shortest path MUTAG 28 17. [sent-239, score-1.201]

92 Table 2: CPU runtime for kernel computation on graph classiﬁcation benchmark datasets factor of 3 slower on D&D. [sent-244, score-0.85]

93 Using larger graphlets with 4 or 5 nodes that might have been more expressive led to infeasible runtime requirements in initial experiments (not shown here). [sent-246, score-0.497]

94 On D&D; the shortest path and graphlet kernels yielded similarly good results, while on NCI1 and NCI109 the Weisfeiler-Lehman kernel improves by more than 8% the best accuracy attained by other methods. [sent-248, score-0.709]

95 We could not assess the performance of the Ramon & G¨ rtner kernel and the random walk kernel on larger datasets, a as their computation did not ﬁnish in 48 hours. [sent-250, score-0.862]

96 The labeled size-3 graphlet kernel achieves low accuracy levels, except on D&D. [sent-251, score-0.471]

97 ; To summarize, the WL kernel turns out to be competitive in terms of runtime on all smaller datasets, fastest on the large protein dataset, and its accuracy levels are highest on three out of four datasets. [sent-252, score-0.693]

98 5 Conclusions We have deﬁned a fast subtree kernel on graphs that combines scalability with the ability to deal with node labels. [sent-253, score-0.977]

99 This new kernel opens the door to applications of graph kernels on large graphs in bioinformatics, for instance, protein function prediction via detailed graph models of protein structure on the amino acid level, or on gene networks for phenotype prediction. [sent-255, score-1.177]

100 An exciting algorithmic question for further studies will be to consider kernels on graphs with continuous or high-dimensional node labels and their efﬁcient computation. [sent-256, score-0.498]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('subtree', 0.406), ('runtime', 0.32), ('kernel', 0.256), ('sh', 0.244), ('graphs', 0.243), ('rtner', 0.228), ('wl', 0.208), ('multiset', 0.191), ('kernels', 0.187), ('graph', 0.171), ('mutag', 0.156), ('nodes', 0.142), ('graphlet', 0.139), ('lh', 0.121), ('strings', 0.119), ('kw', 0.117), ('multisets', 0.104), ('ramon', 0.104), ('string', 0.099), ('height', 0.099), ('walk', 0.098), ('si', 0.097), ('krecursive', 0.087), ('kh', 0.082), ('mh', 0.082), ('hm', 0.081), ('sorting', 0.071), ('neighbourhoods', 0.069), ('protein', 0.062), ('nish', 0.062), ('matchings', 0.061), ('compressed', 0.06), ('sort', 0.059), ('subtrees', 0.059), ('isomorphism', 0.056), ('shortest', 0.055), ('mah', 0.052), ('mutagenic', 0.052), ('nci', 0.052), ('ramong', 0.052), ('pairwise', 0.052), ('counter', 0.049), ('ascending', 0.047), ('days', 0.047), ('labeled', 0.047), ('compounds', 0.046), ('ki', 0.043), ('compression', 0.043), ('hash', 0.043), ('path', 0.043), ('datasets', 0.043), ('counts', 0.043), ('node', 0.042), ('global', 0.04), ('hn', 0.038), ('subgraphs', 0.037), ('benchmark', 0.036), ('borgwardt', 0.035), ('seconds', 0.035), ('aromatic', 0.035), ('debnath', 0.035), ('graphlets', 0.035), ('heteroaromatic', 0.035), ('kramon', 0.035), ('mehlhorn', 0.035), ('nitro', 0.035), ('shervashidze', 0.035), ('walks', 0.034), ('determination', 0.034), ('article', 0.033), ('dataset', 0.031), ('karsten', 0.03), ('bucket', 0.03), ('mapped', 0.03), ('fast', 0.03), ('edges', 0.029), ('patterns', 0.029), ('accuracy', 0.029), ('relabeling', 0.028), ('chemical', 0.028), ('default', 0.027), ('identical', 0.027), ('induction', 0.027), ('labels', 0.026), ('buckets', 0.026), ('concatenate', 0.026), ('competitive', 0.026), ('behaviour', 0.025), ('density', 0.025), ('variant', 0.025), ('label', 0.025), ('amino', 0.025), ('subsample', 0.025), ('classic', 0.024), ('connected', 0.024), ('distinct', 0.024), ('computation', 0.024), ('vishwanathan', 0.023), ('iterations', 0.023), ('scales', 0.022)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999982 95 nips-2009-Fast subtree kernels on graphs

Author: Nino Shervashidze, Karsten M. Borgwardt

2 0.21112007 120 nips-2009-Kernels and learning curves for Gaussian process regression on random graphs

Author: Peter Sollich, Matthew Urry, Camille Coti

Abstract: We investigate how well Gaussian process regression can learn functions deﬁned on graphs, using large regular random graphs as a paradigmatic example. Random-walk based kernels are shown to have some non-trivial properties: within the standard approximation of a locally tree-like graph structure, the kernel does not become constant, i.e. neighbouring function values do not become fully correlated, when the lengthscale σ of the kernel is made large. Instead the kernel attains a non-trivial limiting form, which we calculate. The fully correlated limit is reached only once loops become relevant, and we estimate where the crossover to this regime occurs. Our main subject are learning curves of Bayes error versus training set size. We show that these are qualitatively well predicted by a simple approximation using only the spectrum of a large tree as input, and generically scale with n/V , the number of training examples per vertex. We also explore how this behaviour changes for kernel lengthscales that are large enough for loops to become important. 1 Motivation and Outline Gaussian processes (GPs) have become a standard part of the machine learning toolbox [1]. Learning curves are a convenient way of characterizing their capabilities: they give the generalization error as a function of the number of training examples n, averaged over all datasets of size n under appropriate assumptions about the process generating the data. We focus here on the case of GP regression, where a real-valued output function f (x) is to be learned. The general behaviour of GP learning curves is then relatively well understood for the scenario where the inputs x come from a continuous space, typically Rn [2, 3, 4, 5, 6, 7, 8, 9, 10]. For large n, the learning curves then typically decay as a power law ∝ n−α with an exponent α ≤ 1 that depends on the dimensionality n of the space as well as the smoothness properties of the function f (x) as encoded in the covariance function. But there are many interesting application domains that involve discrete input spaces, where x could be a string, an amino acid sequence (with f (x) some measure of secondary structure or biological function), a research paper (with f (x) related to impact), a web page (with f (x) giving a score used to rank pages), etc. In many such situations, similarity between different inputs – which will govern our prior beliefs about how closely related the corresponding function values are – can be represented by edges in a graph. One would then like to know how well GP regression can work in such problem domains; see also [11] for a related online regression algorithm. We study this 1 problem here theoretically by focussing on the paradigmatic example of random regular graphs, where every node has the same connectivity. Sec. 2 discusses the properties of random-walk inspired kernels [12] on such random graphs. These are analogous to the standard radial basis function kernels exp[−(x − x )2 /(2σ 2 )], but we ﬁnd that they have surprising properties on large graphs. In particular, while loops in large random graphs are long and can be neglected for many purposes, by approximating the graph structure as locally tree-like, here this leads to a non-trivial limiting form of the kernel for σ → ∞ that is not constant. The fully correlated limit, where the kernel is constant, is obtained only because of the presence of loops, and we estimate when the crossover to this regime takes place. In Sec. 3 we move on to the learning curves themselves. A simple approximation based on the graph eigenvalues, using only the known spectrum of a large tree as input, works well qualitatively and predicts the exact asymptotics for large numbers of training examples. When the kernel lengthscale is not too large, below the crossover discussed in Sec. 2 for the covariance kernel, the learning curves depend on the number of examples per vertex. We also explore how this behaviour changes as the kernel lengthscale is made larger. Sec. 4 summarizes the results and discusses some open questions. 2 Kernels on graphs and trees We assume that we are trying to learn a function deﬁned on the vertices of a graph. Vertices are labelled by i = 1 . . . V , instead of the generic input label x we used in the introduction, and the associated function values are denoted fi ∈ R. By taking the prior P (f ) over these functions f = (f1 , . . . , fV ) as a (zero mean) Gaussian process we are saying that P (f ) ∝ exp(− 1 f T C −1 f ). 2 The covariance function or kernel C is then, in our graph setting, just a positive deﬁnite V × V matrix. The graph structure is characterized by a V × V adjacency matrix, with Aij = 1 if nodes i and j are connected by an edge, and 0 otherwise. All links are assumed to be undirected, so that Aij = Aji , V and there are no self-loops (Aii = 0). The degree of each node is then deﬁned as di = j=1 Aij . The covariance kernels we discuss in this paper are the natural generalizations of the squaredexponential kernel in Euclidean space [12]. They can be expressed in terms of the normalized graph Laplacian, deﬁned as L = 1 − D −1/2 AD −1/2 , where D is a diagonal matrix with entries d1 , . . . , dV and 1 is the V × V identity matrix. An advantage of L over the unnormalized Laplacian D − A, which was used in the earlier paper [13], is that the eigenvalues of L (again a V × V matrix) lie in the interval [0,2] (see e.g. [14]). From the graph Laplacian, the covariance kernels we consider here are constructed as follows. The p-step random walk kernel is (for a ≥ 2) C ∝ (1 − a−1 L)p = 1 − a−1 1 + a−1 D −1/2 AD −1/2 p (1) while the diffusion kernel is given by 1 C ∝ exp − 2 σ 2 L ∝ exp 1 2 −1/2 AD −1/2 2σ D (2) We will always normalize these so that (1/V ) i Cii = 1, which corresponds to setting the average (over vertices) prior variance of the function to be learned to unity. To see the connection of the above kernels to random walks, assume we have a walker on the graph who at each time step selects randomly one of the neighbouring vertices and moves to it. The probability for a move from vertex j to i is then Aij /dj . The transition matrix after s steps follows as (AD −1 )s : its ij-element gives the probability of being on vertex i, having started at j. We can now compare this with the p-step kernel by expanding the p-th power in (1): p p ( p )a−s (1−a−1 )p−s (D −1/2 AD −1/2 )s = D −1/2 s C∝ s=0 ( p )a−s (1−a−1 )p−s (AD −1 )s D 1/2 s s=0 (3) Thus C is essentially a random walk transition matrix, averaged over the number of steps s with s ∼ Binomial(p, 1/a) 2 (4) a=2, d=3 K1 1 1 Cl,p 0.9 p=1 p=2 p=3 p=4 p=5 p=10 p=20 p=50 p=100 p=200 p=500 p=infty 0.8 0.6 0.4 d=3 0.8 0.7 0.6 a=2, V=infty a=2, V=500 a=4, V=infty a=4, V=500 0.5 0.4 0.3 0.2 0.2 ln V / ln(d-1) 0.1 0 0 5 10 l 0 15 1 10 p/a 100 1000 Figure 1: (Left) Random walk kernel C ,p plotted vs distance along graph, for increasing number of steps p and a = 2, d = 3. Note the convergence to a limiting shape for large p that is not the naive fully correlated limit C ,p→∞ = 1. (Right) Numerical results for average covariance K1 between neighbouring nodes, averaged over neighbours and over randomly generated regular graphs. This shows that 1/a can be interpreted as the probability of actually taking a step at each of p “attempts”. To obtain the actual C the resulting averaged transition matrix is premultiplied by D −1/2 and postmultiplied by D 1/2 , which ensures that the kernel C is symmetric. For the diffusion kernel, one ﬁnds an analogous result but the number of random walk steps is now distributed as s ∼ Poisson(σ 2 /2). This implies in particular that the diffusion kernel is the limit of the p-step kernel for p, a → ∞ at constant p/a = σ 2 /2. Accordingly, we discuss mainly the p-step kernel in this paper because results for the diffusion kernel can be retrieved as limiting cases. In the limit of a large number of steps s, the random walk on a graph will reach its stationary distribution p∞ ∝ De where e = (1, . . . , 1). (This form of p∞ can be veriﬁed by checking that it remains unchanged after multiplication with the transition matrix AD −1 .) The s-step transition matrix for large s is then p∞ eT = DeeT because we converge from any starting vertex to the stationary distribution. It follows that for large p or σ 2 the covariance kernel becomes C ∝ D 1/2 eeT D 1/2 , i.e. Cij ∝ (di dj )1/2 . This is consistent with the interpretation of σ or (p/a)1/2 as a lengthscale over which the random walk can diffuse along the graph: once this lengthscale becomes large, the covariance kernel Cij is essentially independent of the distance (along the graph) between the vertices i and j, and the function f becomes fully correlated across the graph. (Explicitly f = vD 1/2 e under the prior, with v a single Gaussian random variable.) As we next show, however, the approach to this fully correlated limit as p or σ are increased is non-trivial. We focus in this paper on kernels on random regular graphs. This means we consider adjacency matrices A which are regular in the sense that they give for each vertex the same degree, di = d. A uniform probability distribution is then taken across all A that obey this constraint [15]. What will the above kernels look like on typical samples drawn from this distribution? Such random regular graphs will have long loops, of length of order ln(V ) or larger if V is large. Their local structure is then that of a regular tree of degree d, which suggests that it should be possible to calculate the kernel accurately within a tree approximation. In a regular tree all nodes are equivalent, so the kernel can only depend on the distance between two nodes i and j. Denoting this kernel value C ,p for a p-step random walk kernel, one has then C ,p=0 = δ ,0 and γp+1 C0,p+1 γp+1 C ,p+1 = = 1− 1 ad C 1 a C0,p + −1,p 1 a + 1− C1,p 1 a C (5) ,p + d−1 ad C +1,p for ≥1 (6) where γp is chosen to achieve the desired normalization C0,p = 1 of the prior variance for every p. Fig. 1(left) shows results obtained by iterating this recursion numerically, for a regular graph (in the tree approximation) with degree d = 3, and a = 2. As expected the kernel becomes more longranged initially as p increases, but eventually it is seen to approach a non-trivial limiting form. This can be calculated as C ,p→∞ = [1 + (d − 1)/d](d − 1)− /2 (7) 3 and is also plotted in the ﬁgure, showing good agreement with the numerical iteration. There are (at least) two ways of obtaining the result (7). One is to take the limit σ → ∞ of the integral representation of the diffusion kernel on regular trees given in [16] (which is also quoted in [13] but with a typographical error that effectively removes the factor (d − 1)− /2 ). Another route is to ﬁnd the steady state of the recursion for C ,p . This is easy to do but requires as input the unknown steady state value of γp . To determine this, one can map from C ,p to the total random walk probability S ,p in each “shell” of vertices at distance from the starting vertex, changing variables to S0,p = C0,p and S ,p = d(d − 1) −1 C ,p ( ≥ 1). Omitting the factors γp , this results in a recursion for S ,p that simply describes a biased random walk on = 0, 1, 2, . . ., with a probability of 1 − 1/a of remaining at the current , probability 1/(ad) of moving to the left and probability (d − 1)/(ad) of moving to the right. The point = 0 is a reﬂecting barrier where only moves to the right are allowed, with probability 1/a. The time evolution of this random walk starting from = 0 can now be analysed as in [17]. As expected from the balance of moves to the left and right, S ,p for large p is peaked around the average position of the walk, = p(d − 2)/(ad). For smaller than this S ,p has a tail behaving as ∝ (d − 1) /2 , and converting back to C ,p gives the large- scaling of C ,p→∞ ∝ (d − 1)− /2 ; this in turn ﬁxes the value of γp→∞ and so eventually gives (7). The above analysis shows that for large p the random walk kernel, calculated in the absence of loops, does not approach the expected fully correlated limit; given that all vertices have the same degree, the latter would correspond to C ,p→∞ = 1. This implies, conversely, that the fully correlated limit is reached only because of the presence of loops in the graph. It is then interesting to ask at what point, as p is increased, the tree approximation for the kernel breaks down. To estimate this, we note that a regular tree of depth has V = 1 + d(d − 1) −1 nodes. So a regular graph can be tree-like at most out to ≈ ln(V )/ ln(d − 1). Comparing with the typical number of steps our random walk takes, which is p/a from (4), we then expect loop effects to appear in the covariance kernel when p/a ≈ ln(V )/ ln(d − 1) (8) To check this prediction, we measure the analogue of C1,p on randomly generated [15] regular graphs. Because of the presence of loops, the local kernel values are not all identical, so the appropriate estimate of what would be C1,p on a tree is K1 = Cij / Cii Cjj for neighbouring nodes i and j. Averaging over all pairs of such neighbours, and then over a number of randomly generated graphs we ﬁnd the results in Fig. 1(right). The results for K1 (symbols) accurately track the tree predictions (lines) for small p/a, and start to deviate just around the values of p/a expected from (8), as marked by the arrow. The deviations manifest themselves in larger values of K1 , which eventually – now that p/a is large enough for the kernel to “notice” the loops - approach the fully correlated limit K1 = 1. 3 Learning curves We now turn to the analysis of learning curves for GP regression on random regular graphs. We assume that the target function f ∗ is drawn from a GP prior with a p-step random walk covariance kernel C. Training examples are input-output pairs (iµ , fi∗ + ξµ ) where ξµ is i.i.d. Gaussian noise µ of variance σ 2 ; the distribution of training inputs iµ is taken to be uniform across vertices. Inference from a data set D of n such examples µ = 1, . . . , n takes place using the prior deﬁned by C and a Gaussian likelihood with noise variance σ 2 . We thus assume an inference model that is matched to the data generating process. This is obviously an over-simpliﬁcation but is appropriate for the present ﬁrst exploration of learning curves on random graphs. We emphasize that as n is increased we see more and more function values from the same graph, which is ﬁxed by the problem domain; the graph does not grow. ˆ The generalization error is the squared difference between the estimated function fi and the target fi∗ , averaged across the (uniform) input distribution, the posterior distribution of f ∗ given D, the distribution of datasets D, and ﬁnally – in our non-Euclidean setting – the random graph ensemble. Given the assumption of a matched inference model, this is just the average Bayes error, or the average posterior variance, which can be expressed explicitly as [1] (n) = V −1 Cii − k(i)T Kk−1 (i) i 4 D,graphs (9) where the average is over data sets and over graphs, K is an n × n matrix with elements Kµµ = Ciµ ,iµ + σ 2 δµµ and k(i) is a vector with entries kµ (i) = Ci,iµ . The resulting learning curve depends, in addition to n, on the graph structure as determined by V and d, and the kernel and noise level as speciﬁed by p, a and σ 2 . We ﬁx d = 3 throughout to avoid having too many parameters to vary, although similar results are obtained for larger d. Exact prediction of learning curves by analytical calculation is very difﬁcult due to the complicated way in which the random selection of training inputs enters the matrix K and vector k in (9). However, by ﬁrst expressing these quantities in terms of kernel eigenvalues (see below) and then approximating the average over datasets, one can derive the approximation [3, 6] =g n + σ2 V , g(h) = (λ−1 + h)−1 α (10) α=1 This equation for has to be solved self-consistently because also appears on the r.h.s. In the Euclidean case the resulting predictions approximate the true learning curves quite reliably. The derivation of (10) for inputs on a ﬁxed graph is unchanged from [3], provided the kernel eigenvalues λα appearing in the function g(h) are deﬁned appropriately, by the eigenfunction condition Cij φj = λφi ; the average here is over the input distribution, i.e. . . . = V −1 j . . . From the deﬁnition (1) of the p-step kernel, we see that then λα = κV −1 (1 − λL /a)p in terms of the corα responding eigenvalue of the graph Laplacian L. The constant κ has to be chosen to enforce our normalization convention α λα = Cjj = 1. Fortunately, for large V the spectrum of the Laplacian of a random regular graph can be approximated by that of the corresponding large regular tree, which has spectral density [14] L ρ(λ ) = 4(d−1) − (λL − 1)2 d2 2πdλL (2 − λL ) (11) in the range λL ∈ [λL , λL ], λL = 1 + 2d−1 (d − 1)1/2 , where the term under the square root is ± + − positive. (There are also two isolated eigenvalues λL = 0, 2 but these have weight 1/V each and so can be ignored for large V .) Rewriting (10) as = V −1 α [(V λα )−1 + (n/V )( + σ 2 )−1 ]−1 and then replacing the average over kernel eigenvalues by an integral over the spectral density leads to the following prediction for the learning curve: = dλL ρ(λL )[κ−1 (1 − λL /a)−p + ν/( + σ 2 )]−1 (12) with κ determined from κ dλL ρ(λL )(1 − λL /a)p = 1. A general consequence of the form of this result is that the learning curve depends on n and V only through the ratio ν = n/V , i.e. the number of training examples per vertex. The approximation (12) also predicts that the learning curve will have two regimes, one for small ν where σ 2 and the generalization error will be essentially 2 independent of σ ; and another for large ν where σ 2 so that can be neglected on the r.h.s. and one has a fully explicit expression for . We compare the above prediction in Fig. 2(left) to the results of numerical simulations of the learning curves, averaged over datasets and random regular graphs. The two regimes predicted by the approximation are clearly visible; the approximation works well inside each regime but less well in the crossover between the two. One striking observation is that the approximation seems to predict the asymptotic large-n behaviour exactly; this is distinct to the Euclidean case, where generally only the power-law of the n-dependence but not its prefactor come out accurately. To see why, we exploit that for large n (where σ 2 ) the approximation (9) effectively neglects ﬂuctuations in the training input “density” of a randomly drawn set of training inputs [3, 6]. This is justiﬁed in the graph case for large ν = n/V , because the number of training inputs each vertex receives, Binomial(n, 1/V ), has negligible relative ﬂuctuations away from its mean ν. In the Euclidean case there is no similar result, because all training inputs are different with probability one even for large n. Fig. 2(right) illustrates that for larger a the difference in the crossover region between the true (numerically simulated) learning curves and our approximation becomes larger. This is because the average number of steps p/a of the random walk kernel then decreases: we get closer to the limit of uncorrelated function values (a → ∞, Cij = δij ). In that limit and for low σ 2 and large V the 5 V=500 (filled) & 1000 (empty), d=3, a=2, p=10 V=500, d=3, a=4, p=10 0 0 10 10 ε ε -1 -1 10 10 -2 10 -2 10 2 σ = 0.1 2 σ = 0.1 2 -3 10 σ = 0.01 2 σ = 0.01 -3 10 2 σ = 0.001 2 σ = 0.001 2 -4 10 2 σ = 0.0001 σ = 0.0001 -4 10 2 σ =0 -5 2 σ =0 -5 10 0.1 1 ν=n/V 10 10 0.1 1 ν=n/V 10 Figure 2: (Left) Learning curves for GP regression on random regular graphs with degree d = 3 and V = 500 (small ﬁlled circles) and V = 1000 (empty circles) vertices. Plotting generalization error versus ν = n/V superimposes the results for both values of V , as expected from the approximation (12). The lines are the quantitative predictions of this approximation. Noise level as shown, kernel parameters a = 2, p = 10. (Right) As on the left but with V = 500 only and for larger a = 4. 2 V=500, d=3, a=2, p=20 0 0 V=500, d=3, a=2, p=200, σ =0.1 10 10 ε ε simulation -1 2 10 1/(1+n/σ ) theory (tree) theory (eigenv.) -1 10 -2 10 2 σ = 0.1 -3 10 -4 10 -2 10 2 σ = 0.01 2 σ = 0.001 2 σ = 0.0001 -3 10 2 σ =0 -5 10 -4 0.1 1 ν=n/V 10 10 1 10 100 n 1000 10000 Figure 3: (Left) Learning curves for GP regression on random regular graphs with degree d = 3 and V = 500, and kernel parameters a = 2, p = 20; noise level σ 2 as shown. Circles: numerical simulations; lines: approximation (12). (Right) As on the left but for much larger p = 200 and for a single random graph, with σ 2 = 0.1. Dotted line: naive estimate = 1/(1 + n/σ 2 ). Dashed line: approximation (10) using the tree spectrum and the large p-limit, see (17). Solid line: (10) with numerically determined graph eigenvalues λL as input. α true learning curve is = exp(−ν), reﬂecting the probability of a training input set not containing a particular vertex, while the approximation can be shown to predict = max{1 − ν, 0}, i.e. a decay of the error to zero at ν = 1. Plotting these two curves (not displayed here) indeed shows the same “shape” of disagreement as in Fig. 2(right), with the approximation underestimating the true generalization error. Increasing p has the effect of making the kernel longer ranged, giving an effect opposite to that of increasing a. In line with this, larger values of p improve the accuracy of the approximation (12): see Fig. 3(left). One may ask about the shape of the learning curves for large number of training examples (per vertex) ν. The roughly straight lines on the right of the log-log plots discussed so far suggest that ∝ 1/ν in this regime. This is correct in the mathematical limit ν → ∞ because the graph kernel has a nonzero minimal eigenvalue λ− = κV −1 (1−λL /a)p : for ν σ 2 /(V λ− ), the square bracket + 6 in (12) can then be approximated by ν/( +σ 2 ) and one gets (because also regime) ≈ σ 2 /ν. σ 2 in the asymptotic However, once p becomes reasonably large, V λ− can be shown – by analysing the scaling of κ, see Appendix – to be extremely (exponentially in p) small; for the parameter values in Fig. 3(left) it is around 4 × 10−30 . The “terminal” asymptotic regime ≈ σ 2 /ν is then essentially unreachable. A more detailed analysis of (12) for large p and large (but not exponentially large) ν, as sketched in the Appendix, yields ∝ (cσ 2 /ν) ln3/2 (ν/(cσ 2 )), c ∝ p−3/2 (13) This shows that there are logarithmic corrections to the naive σ 2 /ν scaling that would apply in the true terminal regime. More intriguing is the scaling of the coefﬁcient c with p, which implies that to reach a speciﬁed (low) generalization error one needs a number of training examples per vertex of order ν ∝ cσ 2 ∝ p−3/2 σ 2 . Even though the covariance kernel C ,p – in the same tree approximation that also went into (12) – approaches a limiting form for large p as discussed in Sec. 2, generalization performance thus continues to improve with increasing p. The explanation for this must presumably be that C ,p converges to the limit (7) only at ﬁxed , while in the tail ∝ p, it continues to change. For ﬁnite graph sizes V we know of course that loops will eventually become important as p increases, around the crossover point estimated in (8). The approximation for the learning curve in (12) should then break down. The most naive estimate beyond this point would be to say that the kernel becomes nearly fully correlated, Cij ∝ (di dj )1/2 which in the regular case simpliﬁes to Cij = 1. With only one function value to learn, and correspondingly only one nonzero kernel eigenvalue λα=1 = 1, one would predict = 1/(1 + n/σ 2 ). Fig. 3(right) shows, however, that this signiﬁcantly underestimates the actual generalization error, even though for this graph λα=1 = 0.994 is very close to unity so that the other eigenvalues sum to no more than 0.006. An almost perfect prediction is obtained, on the other hand, from the approximation (10) with the numerically calculated values of the Laplacian – and hence kernel – eigenvalues. The presence of the small kernel eigenvalues is again seen to cause logarithmic corrections to the naive ∝ 1/n scaling. Using the tree spectrum as an approximation and exploiting the large-p limit, one ﬁnds indeed (see Appendix, Eq. (17)) that ∝ (c σ 2 /n) ln3/2 (n/c σ 2 ) where now n enters rather than ν = n/V , c being a constant dependent only on p and a: informally, the function to be learned only has a ﬁnite (rather than ∝ V ) number of degrees of freedom. The approximation (17) in fact provides a qualitatively accurate description of the data Fig. 3(right), as the dashed line in the ﬁgure shows. We thus have the somewhat unusual situation that the tree spectrum is enough to give a good description of the learning curves even when loops are important, while (see Sec. 2) this is not so as far as the evaluation of the covariance kernel itself is concerned. 4 Summary and Outlook We have studied theoretically the generalization performance of GP regression on graphs, focussing on the paradigmatic case of random regular graphs where every vertex has the same degree d. Our initial concern was with the behaviour of p-step random walk kernels on such graphs. If these are calculated within the usual approximation of a locally tree-like structure, then they converge to a non-trivial limiting form (7) when p – or the corresponding lengthscale σ in the closely related diffusion kernel – becomes large. The limit of full correlation between all function values on the graph is only reached because of the presence of loops, and we have estimated in (8) the values of p around which the crossover to this loop-dominated regime occurs; numerical data for correlations of function values on neighbouring vertices support this result. In the second part of the paper we concentrated on the learning curves themselves. We assumed that inference is performed with the correct parameters describing the data generating process; the generalization error is then just the Bayes error. The approximation (12) gives a good qualitative description of the learning curve using only the known spectrum of a large regular tree as input. It predicts in particular that the key parameter that determines the generalization error is ν = n/V , the number of training examples per vertex. We demonstrated also that the approximation is in fact more useful than in the Euclidean case because it gives exact asymptotics for the limit ν 1. Quantitatively, we found that the learning curves decay as ∝ σ 2 /ν with non-trivial logarithmic correction terms. Slower power laws ∝ ν −α with α < 1, as in the Euclidean case, do not appear. 7 We attribute this to the fact that on a graph there is no analogue of the local roughness of a target function because there is a minimum distance (one step along the graph) between different input points. Finally we looked at the learning curves for larger p, where loops become important. These can still be predicted quite accurately by using the tree eigenvalue spectrum as an approximation, if one keeps track of the zero graph Laplacian eigenvalue which we were able to ignore previously; the approximation shows that the generalization error scales as σ 2 /n with again logarithmic corrections. In future work we plan to extend our analysis to graphs that are not regular, including ones from application domains as well as artiﬁcial ones with power-law tails in the distribution of degrees d, where qualitatively new effects are to be expected. It would also be desirable to improve the predictions for the learning curve in the crossover region ≈ σ 2 , which should be achievable using iterative approaches based on belief propagation that have already been shown to give accurate approximations for graph eigenvalue spectra [18]. These tools could then be further extended to study e.g. the effects of model mismatch in GP regression on random graphs, and how these are mitigated by tuning appropriate hyperparameters. Appendix We sketch here how to derive (13) from (12) for large p. Eq. (12) writes = g(νV /( + σ 2 )) with λL + g(h) = dλL ρ(λL )[κ−1 (1 − λL /a)−p + hV −1 ]−1 (14) λL − and κ determined from the condition g(0) = 1. (This g(h) is the tree spectrum approximation to the g(h) of (10).) Turning ﬁrst to g(0), the factor (1 − λL /a)p decays quickly to zero as λL increases above λL . One can then approximate this factor according to (1 − λL /a)p [(a − λL )/(a − λL )]p ≈ − − − (1 − λL /a)p exp[−(λL − λL )p/(a − λL )]. In the regime near λL one can also approximate the − − − − spectral density (11) by its leading square-root increase, ρ(λL ) = r(λL − λL )1/2 , with r = (d − − 1)1/4 d5/2 /[π(d − 2)2 ]. Switching then to a new integration variable y = (λL − λL )p/(a − λL ) and − − extending the integration limit to ∞ gives ∞ √ 1 = g(0) = κr(1 − λL /a)p [p/(a − λL )]−3/2 dy y e−y (15) − − 0 and this ﬁxes κ. Proceeding similarly for h > 0 gives ∞ g(h) = κr(1−λL /a)p [p/(a−λL )]−3/2 F (hκV −1 (1−λL /a)p ), − − − F (z) = √ dy y (ey +z)−1 0 (16) Dividing by g(0) = 1 shows that simply g(h) = F (hV −1 c−1 )/F (0), where c = 1/[κ(1 − σ2 λL /a)p ] = rF (0)[p/(a − λL )]−3/2 which scales as p−3/2 . In the asymptotic regime − − 2 2 we then have = g(νV /σ ) = F (ν/(cσ ))/F (0) and the desired result (13) follows from the large-z behaviour of F (z) ≈ z −1 ln3/2 (z). One can proceed similarly for the regime where loops become important. Clearly the zero Laplacian eigenvalue with weight 1/V then has to be taken into account. If we assume that the remainder of the Laplacian spectrum can still be approximated by that of a tree [18], we get (V + hκ)−1 + r(1 − λL /a)p [p/(a − λL )]−3/2 F (hκV −1 (1 − λL /a)p ) − − − g(h) = (17) V −1 + r(1 − λL /a)p [p/(a − λL )]−3/2 F (0) − − The denominator here is κ−1 and the two terms are proportional respectively to the covariance kernel eigenvalue λ1 , corresponding to λL = 0 and the constant eigenfunction, and to 1−λ1 . Dropping the 1 ﬁrst terms in the numerator and denominator of (17) by taking V → ∞ leads back to the previous analysis as it should. For a situation as in Fig. 3(right), on the other hand, where λ1 is close to unity, we have κ ≈ V and so g(h) ≈ (1 + h)−1 + rV (1 − λL /a)p [p/(a − λL )]−3/2 F (h(1 − λL /a)p ) (18) − − − The second term, coming from the small kernel eigenvalues, is the more slowly decaying because it corresponds to ﬁne detail of the target function that needs many training examples to learn accurately. It will therefore dominate the asymptotic behaviour of the learning curve: = g(n/σ 2 ) ∝ F (n/(c σ 2 )) with c = (1 − λL /a)−p independent of V . The large-n tail of the learning curve in − Fig. 3(right) is consistent with this form. 8 References [1] C E Rasmussen and C K I Williams. Gaussian processes for regression. In D S Touretzky, M C Mozer, and M E Hasselmo, editors, Advances in Neural Information Processing Systems 8, pages 514–520, Cambridge, MA, 1996. MIT Press. [2] M Opper. Regression with Gaussian processes: Average case performance. In I K Kwok-Yee, M Wong, I King, and Dit-Yun Yeung, editors, Theoretical Aspects of Neural Computation: A Multidisciplinary Perspective, pages 17–23. Springer, 1997. [3] P Sollich. Learning curves for Gaussian processes. In M S Kearns, S A Solla, and D A Cohn, editors, Advances in Neural Information Processing Systems 11, pages 344–350, Cambridge, MA, 1999. MIT Press. [4] M Opper and F Vivarelli. General bounds on Bayes errors for regression with Gaussian processes. In M Kearns, S A Solla, and D Cohn, editors, Advances in Neural Information Processing Systems 11, pages 302–308, Cambridge, MA, 1999. MIT Press. [5] C K I Williams and F Vivarelli. Upper and lower bounds on the learning curve for Gaussian processes. Mach. Learn., 40(1):77–102, 2000. [6] D Malzahn and M Opper. Learning curves for Gaussian processes regression: A framework for good approximations. In T K Leen, T G Dietterich, and V Tresp, editors, Advances in Neural Information Processing Systems 13, pages 273–279, Cambridge, MA, 2001. MIT Press. [7] D Malzahn and M Opper. A variational approach to learning curves. In T G Dietterich, S Becker, and Z Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 463–469, Cambridge, MA, 2002. MIT Press. [8] P Sollich and A Halees. Learning curves for Gaussian process regression: approximations and bounds. Neural Comput., 14(6):1393–1428, 2002. [9] P Sollich. Gaussian process regression with mismatched models. In T G Dietterich, S Becker, and Z Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 519–526, Cambridge, MA, 2002. MIT Press. [10] P Sollich. Can Gaussian process regression be made robust against model mismatch? In Deterministic and Statistical Methods in Machine Learning, volume 3635 of Lecture Notes in Artiﬁcial Intelligence, pages 199–210. 2005. [11] M Herbster, M Pontil, and L Wainer. Online learning over graphs. In ICML ’05: Proceedings of the 22nd international conference on Machine learning, pages 305–312, New York, NY, USA, 2005. ACM. [12] A J Smola and R Kondor. Kernels and regularization on graphs. In M Warmuth and B Sch¨ lkopf, o editors, Proc. Conference on Learning Theory (COLT), Lect. Notes Comp. Sci., pages 144–158. Springer, Heidelberg, 2003. [13] R I Kondor and J D Lafferty. Diffusion kernels on graphs and other discrete input spaces. In ICML ’02: Proceedings of the Nineteenth International Conference on Machine Learning, pages 315–322, San Francisco, CA, USA, 2002. Morgan Kaufmann. [14] F R K Chung. Spectral graph theory. Number 92 in Regional Conference Series in Mathematics. Americal Mathematical Society, 1997. [15] A Steger and N C Wormald. Generating random regular graphs quickly. Combinator. Probab. Comput., 8(4):377–396, 1999. [16] F Chung and S-T Yau. Coverings, heat kernels and spanning trees. The Electronic Journal of Combinatorics, 6(1):R12, 1999. [17] C Monthus and C Texier. Random walk on the Bethe lattice and hyperbolic brownian motion. J. Phys. A, 29(10):2399–2409, 1996. [18] T Rogers, I Perez Castillo, R Kuehn, and K Takeda. Cavity approach to the spectral density of sparse symmetric random matrices. Phys. Rev. E, 78(3):031116, 2008. 9

3 0.20646319 139 nips-2009-Linear-time Algorithms for Pairwise Statistical Problems

Author: Parikshit Ram, Dongryeol Lee, William March, Alexander G. Gray

Abstract: Several key computational bottlenecks in machine learning involve pairwise distance computations, including all-nearest-neighbors (ďŹ nding the nearest neighbor(s) for each point, e.g. in manifold learning) and kernel summations (e.g. in kernel density estimation or kernel machines). We consider the general, bichromatic case for these problems, in addition to the scientiďŹ c problem of N-body simulation. In this paper we show for the ďŹ rst time O(đ?‘ ) worst case runtimes for practical algorithms for these problems based on the cover tree data structure [1]. 1

4 0.15278181 128 nips-2009-Learning Non-Linear Combinations of Kernels

Author: Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh

Abstract: This paper studies the general problem of learning kernels based on a polynomial combination of base kernels. We analyze this problem in the case of regression and the kernel ridge regression algorithm. We examine the corresponding learning kernel optimization problem, show how that minimax problem can be reduced to a simpler minimization problem, and prove that the global solution of this problem always lies on the boundary. We give a projection-based gradient descent algorithm for solving the optimization problem, shown empirically to converge in few iterations. Finally, we report the results of extensive experiments with this algorithm using several publicly available datasets demonstrating the effectiveness of our technique.

5 0.13229991 119 nips-2009-Kernel Methods for Deep Learning

Author: Youngmin Cho, Lawrence K. Saul

Abstract: We introduce a new family of positive-deﬁnite kernel functions that mimic the computation in large, multilayer neural nets. These kernel functions can be used in shallow architectures, such as support vector machines (SVMs), or in deep kernel-based architectures that we call multilayer kernel machines (MKMs). We evaluate SVMs and MKMs with these kernel functions on problems designed to illustrate the advantages of deep architectures. On several problems, we obtain better results than previous, leading benchmarks from both SVMs with Gaussian kernels as well as deep belief nets. 1

6 0.11681519 118 nips-2009-Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions

7 0.10575151 77 nips-2009-Efficient Match Kernel between Sets of Features for Visual Recognition

8 0.089375585 122 nips-2009-Label Selection on Graphs

9 0.086852364 23 nips-2009-Accelerating Bayesian Structural Inference for Non-Decomposable Gaussian Graphical Models

10 0.08237087 80 nips-2009-Efficient and Accurate Lp-Norm Multiple Kernel Learning

11 0.081795014 141 nips-2009-Local Rules for Global MAP: When Do They Work ?

12 0.078717113 207 nips-2009-Robust Nonparametric Regression with Metric-Space Valued Output

13 0.077806823 87 nips-2009-Exponential Family Graph Matching and Ranking

14 0.074170299 148 nips-2009-Matrix Completion from Power-Law Distributed Samples

15 0.072115719 179 nips-2009-On the Algorithmics and Applications of a Mixed-norm based Kernel Learning Formulation

16 0.070190303 92 nips-2009-Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming

17 0.068137042 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification

18 0.066738114 256 nips-2009-Which graphical models are difficult to learn?

19 0.066638872 72 nips-2009-Distribution Matching for Transduction

20 0.064477101 8 nips-2009-A Fast, Consistent Kernel Two-Sample Test

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.173), (1, 0.086), (2, -0.086), (3, 0.1), (4, -0.124), (5, -0.104), (6, -0.05), (7, 0.209), (8, -0.174), (9, -0.119), (10, 0.028), (11, -0.102), (12, 0.064), (13, 0.058), (14, -0.079), (15, 0.094), (16, -0.057), (17, 0.036), (18, 0.053), (19, -0.008), (20, 0.122), (21, 0.117), (22, 0.061), (23, 0.105), (24, 0.053), (25, 0.049), (26, 0.023), (27, -0.09), (28, -0.02), (29, -0.147), (30, -0.027), (31, -0.051), (32, -0.145), (33, -0.019), (34, -0.079), (35, 0.012), (36, 0.065), (37, 0.153), (38, 0.049), (39, 0.01), (40, 0.049), (41, 0.027), (42, -0.024), (43, 0.01), (44, -0.018), (45, -0.019), (46, -0.005), (47, -0.004), (48, -0.033), (49, 0.111)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97983998 95 nips-2009-Fast subtree kernels on graphs

Author: Nino Shervashidze, Karsten M. Borgwardt

2 0.77587152 120 nips-2009-Kernels and learning curves for Gaussian process regression on random graphs

Author: Peter Sollich, Matthew Urry, Camille Coti

3 0.6592809 139 nips-2009-Linear-time Algorithms for Pairwise Statistical Problems

Author: Parikshit Ram, Dongryeol Lee, William March, Alexander G. Gray

4 0.65775168 128 nips-2009-Learning Non-Linear Combinations of Kernels

Author: Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh

5 0.63036329 119 nips-2009-Kernel Methods for Deep Learning

Author: Youngmin Cho, Lawrence K. Saul

6 0.58173954 118 nips-2009-Kernel Choice and Classifiability for RKHS Embeddings of Probability Distributions

7 0.58117384 77 nips-2009-Efficient Match Kernel between Sets of Features for Visual Recognition

8 0.57126415 92 nips-2009-Fast Graph Laplacian Regularized Kernel Learning via Semidefinite–Quadratic–Linear Programming

9 0.4606199 122 nips-2009-Label Selection on Graphs

10 0.45586106 8 nips-2009-A Fast, Consistent Kernel Two-Sample Test

11 0.43196198 143 nips-2009-Localizing Bugs in Program Executions with Graphical Models

12 0.42710721 249 nips-2009-Tracking Dynamic Sources of Malicious Activity at Internet Scale

13 0.42006713 141 nips-2009-Local Rules for Global MAP: When Do They Work ?

14 0.41343009 23 nips-2009-Accelerating Bayesian Structural Inference for Non-Decomposable Gaussian Graphical Models

15 0.41276768 148 nips-2009-Matrix Completion from Power-Law Distributed Samples

16 0.40621349 64 nips-2009-Data-driven calibration of linear estimators with minimal penalties

17 0.40419373 149 nips-2009-Maximin affinity learning of image segmentation

18 0.39410582 256 nips-2009-Which graphical models are difficult to learn?

19 0.38216212 80 nips-2009-Efficient and Accurate Lp-Norm Multiple Kernel Learning

20 0.36608905 82 nips-2009-Entropic Graph Regularization in Non-Parametric Semi-Supervised Classification

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.408), (21, 0.011), (24, 0.031), (25, 0.041), (35, 0.024), (36, 0.107), (39, 0.048), (58, 0.038), (71, 0.051), (81, 0.014), (86, 0.141)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.89583659 165 nips-2009-Noise Characterization, Modeling, and Reduction for In Vivo Neural Recording

Author: Zhi Yang, Qi Zhao, Edward Keefer, Wentai Liu

Abstract: Studying signal and noise properties of recorded neural data is critical in developing more efﬁcient algorithms to recover the encoded information. Important issues exist in this research including the variant spectrum spans of neural spikes that make it difﬁcult to choose a globally optimal bandpass ﬁlter. Also, multiple sources produce aggregated noise that deviates from the conventional white Gaussian noise. In this work, the spectrum variability of spikes is addressed, based on which the concept of adaptive bandpass ﬁlter that ﬁts the spectrum of individual spikes is proposed. Multiple noise sources have been studied through analytical models as well as empirical measurements. The dominant noise source is identiﬁed as neuron noise followed by interface noise of the electrode. This suggests that major efforts to reduce noise from electronics are not well spent. The measured noise from in vivo experiments shows a family of 1/f x spectrum that can be reduced using noise shaping techniques. In summary, the methods of adaptive bandpass ﬁltering and noise shaping together result in several dB signal-to-noise ratio (SNR) enhancement.

same-paper 2 0.82216156 95 nips-2009-Fast subtree kernels on graphs

Author: Nino Shervashidze, Karsten M. Borgwardt

3 0.7367844 170 nips-2009-Nonlinear directed acyclic structure learning with weakly additive noise models

Author: Arthur Gretton, Peter Spirtes, Robert E. Tillman

Abstract: The recently proposed additive noise model has advantages over previous directed structure learning approaches since it (i) does not assume linearity or Gaussianity and (ii) can discover a unique DAG rather than its Markov equivalence class. However, for certain distributions, e.g. linear Gaussians, the additive noise model is invertible and thus not useful for structure learning, and it was originally proposed for the two variable case with a multivariate extension which requires enumerating all possible DAGs. We introduce weakly additive noise models, which extends this framework to cases where the additive noise model is invertible and when additive noise is not present. We then provide an algorithm that learns an equivalence class for such models from data, by combining a PC style search using recent advances in kernel measures of conditional dependence with local searches for additive noise models in substructures of the Markov equivalence class. This results in a more computationally eﬃcient approach that is useful for arbitrary distributions even when additive noise models are invertible. 1

4 0.73371172 69 nips-2009-Discrete MDL Predicts in Total Variation

Author: Marcus Hutter

Abstract: The Minimum Description Length (MDL) principle selects the model that has the shortest code for data plus model. We show that for a countable class of models, MDL predictions are close to the true distribution in a strong sense. The result is completely general. No independence, ergodicity, stationarity, identiﬁability, or other assumption on the model class need to be made. More formally, we show that for any countable class of models, the distributions selected by MDL (or MAP) asymptotically predict (merge with) the true measure in the class in total variation distance. Implications for non-i.i.d. domains like time-series forecasting, discriminative learning, and reinforcement learning are discussed. 1

5 0.66935599 80 nips-2009-Efficient and Accurate Lp-Norm Multiple Kernel Learning

Author: Marius Kloft, Ulf Brefeld, Pavel Laskov, Klaus-Robert Müller, Alexander Zien, Sören Sonnenburg

Abstract: Learning linear combinations of multiple kernels is an appealing strategy when the right choice of features is unknown. Previous approaches to multiple kernel learning (MKL) promote sparse kernel combinations to support interpretability. Unfortunately, 1 -norm MKL is hardly observed to outperform trivial baselines in practical applications. To allow for robust kernel mixtures, we generalize MKL to arbitrary p -norms. We devise new insights on the connection between several existing MKL formulations and develop two efﬁcient interleaved optimization strategies for arbitrary p > 1. Empirically, we demonstrate that the interleaved optimization strategies are much faster compared to the traditionally used wrapper approaches. Finally, we apply p -norm MKL to real-world problems from computational biology, showing that non-sparse MKL achieves accuracies that go beyond the state-of-the-art. 1

6 0.59324586 17 nips-2009-A Sparse Non-Parametric Approach for Single Channel Separation of Known Sounds

7 0.45121109 237 nips-2009-Subject independent EEG-based BCI decoding

8 0.45110768 210 nips-2009-STDP enables spiking neurons to detect hidden causes of their inputs

9 0.44545862 32 nips-2009-An Online Algorithm for Large Scale Image Similarity Learning

10 0.43841374 226 nips-2009-Spatial Normalized Gamma Processes

11 0.43029046 99 nips-2009-Functional network reorganization in motor cortex can be explained by reward-modulated Hebbian learning

12 0.42507187 13 nips-2009-A Neural Implementation of the Kalman Filter

13 0.4248057 162 nips-2009-Neural Implementation of Hierarchical Bayesian Inference by Importance Sampling

14 0.42245686 3 nips-2009-AUC optimization and the two-sample problem

15 0.42211103 175 nips-2009-Occlusive Components Analysis

16 0.42153284 119 nips-2009-Kernel Methods for Deep Learning

17 0.42102587 217 nips-2009-Sharing Features among Dynamical Systems with Beta Processes

18 0.42018154 253 nips-2009-Unsupervised feature learning for audio classification using convolutional deep belief networks

19 0.41853189 176 nips-2009-On Invariance in Hierarchical Models

20 0.4181636 111 nips-2009-Hierarchical Modeling of Local Image Features through $L p$-Nested Symmetric Distributions