Graph Kernels via Functional Embedding

Graph Kernels via Functional Embedding. Shrivastava, A. & Li, P. CoRR, 2014.

We propose a representation of graph as a functional object derived from the power iteration of the underlying adjacency matrix. The proposed functional representation is a graph invariant, i.e., the functional remains unchanged under any reordering of the vertices. This property eliminates the difficulty of handling exponentially many isomorphic forms. Bhattacharyya kernel constructed between these functionals significantly outperforms the state-of-the-art graph kernels on 3 out of the 4 standard benchmark graph classification datasets, demonstrating the superiority of our approach. The proposed methodology is simple and runs in time linear in the number of edges, which makes our kernel more efficient and scalable compared to many widely adopted graph kernels with running time cubic in the number of vertices.

@article{ DBLP:journals/corr/Shrivastava014,
  title = {Graph Kernels via Functional Embedding},
  author = {Anshumali Shrivastava and  Ping Li},
  journal = {CoRR},
  year = {2014},
  volume = {abs/1404.5214},
  url = {http://arxiv.org/abs/1404.5214},
  owner = {vilhuber},
  abstract = {We propose a representation of graph as a functional object derived from the power iteration of the underlying adjacency matrix. The proposed functional representation is a graph invariant, i.e., the functional remains unchanged under any reordering of the vertices. This property eliminates the difficulty of handling exponentially many isomorphic forms. Bhattacharyya kernel constructed between these functionals significantly outperforms the state-of-the-art graph kernels on 3 out of the 4 standard benchmark graph classification datasets, demonstrating the superiority of our approach. The proposed methodology is simple and runs in time linear in the number of edges, which makes our kernel more efficient and scalable compared to many widely adopted graph kernels with running time cubic in the number of vertices.},
  timestamp = {2014.07.09}
}

Downloads: 0

{"_id":"6DDQAMK4miksPhtT6","authorIDs":[],"author_short":["Shrivastava, A.","Li, P."],"bibbaseid":"shrivastava-li-graphkernelsviafunctionalembedding-2014","bibdata":{"abstract":"We propose a representation of graph as a functional object derived from the power iteration of the underlying adjacency matrix. The proposed functional representation is a graph invariant, i.e., the functional remains unchanged under any reordering of the vertices. This property eliminates the difficulty of handling exponentially many isomorphic forms. Bhattacharyya kernel constructed between these functionals significantly outperforms the state-of-the-art graph kernels on 3 out of the 4 standard benchmark graph classification datasets, demonstrating the superiority of our approach. The proposed methodology is simple and runs in time linear in the number of edges, which makes our kernel more efficient and scalable compared to many widely adopted graph kernels with running time cubic in the number of vertices.","author":["Shrivastava, Anshumali","Li, Ping"],"author_short":["Shrivastava, A.","Li, P."],"bibtex":"@article{ DBLP:journals/corr/Shrivastava014,\n title = {Graph Kernels via Functional Embedding},\n author = {Anshumali Shrivastava and Ping Li},\n journal = {CoRR},\n year = {2014},\n volume = {abs/1404.5214},\n url = {http://arxiv.org/abs/1404.5214},\n owner = {vilhuber},\n abstract = {We propose a representation of graph as a functional object derived from the power iteration of the underlying adjacency matrix. The proposed functional representation is a graph invariant, i.e., the functional remains unchanged under any reordering of the vertices. This property eliminates the difficulty of handling exponentially many isomorphic forms. Bhattacharyya kernel constructed between these functionals significantly outperforms the state-of-the-art graph kernels on 3 out of the 4 standard benchmark graph classification datasets, demonstrating the superiority of our approach. The proposed methodology is simple and runs in time linear in the number of edges, which makes our kernel more efficient and scalable compared to many widely adopted graph kernels with running time cubic in the number of vertices.},\n timestamp = {2014.07.09}\n}","bibtype":"article","id":"DBLP:journals/corr/Shrivastava014","journal":"CoRR","key":"DBLP:journals/corr/Shrivastava014","owner":"vilhuber","timestamp":"2014.07.09","title":"Graph Kernels via Functional Embedding","type":"article","url":"http://arxiv.org/abs/1404.5214","volume":"abs/1404.5214","year":"2014","bibbaseid":"shrivastava-li-graphkernelsviafunctionalembedding-2014","role":"author","urls":{"Paper":"http://arxiv.org/abs/1404.5214"},"downloads":0,"html":""},"bibtype":"article","biburl":"http://www.ncrn.cornell.edu/images/bibtex/nsf-1131848.bib","creationDate":"2014-12-11T13:34:22.777Z","downloads":0,"keywords":[],"search_terms":["graph","kernels","via","functional","embedding","shrivastava","li"],"title":"Graph Kernels via Functional Embedding","year":2014,"dataSources":["hxSRj7opbnmFRzHzF"]}