Natural language processing often involves computations with semantic orsyntactic graphs to facilitate sophisticated reasoning based on structuralrelationships. While convolution kernels provide a powerful tool for comparinggraph structure based on node (word) level relationships, they are difficult tocustomize and can be computationally expensive. We propose a generalization ofconvolution kernels, with a nonstationary model, for better expressibility ofnatural languages in supervised settings. For a scalable learning of theparameters introduced with our model, we propose a novel algorithm thatleverages stochastic sampling on k-nearest neighbor graphs, along withapproximations based on locality-sensitive hashing. We demonstrate theadvantages of our approach on a challenging real-world (structured inference)problem of automatically extracting biological models from the text ofscientific papers.