A Hypergraph Kernel from Isomorphism Tests

Lu Bai, Peng Ren, Edwin R. Hancock

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we present a hypergraph kernel computed using substructure isomorphism tests. Measuring the isomorphisms between hypergraphs straightforwardly tends to be elusive since a hypergraph may exhibit varying relational orders. We thus transform a hypergraph into a directed line graph. This not only accurately reflects the multiple relationships exhibited by the hypergraph but is also easier to manipulate isomorphism tests. To locate the isomorphisms between hypergraphs through their directed line graphs, we propose a new directed Weisfeiler-Lehman isomorphism test for directed graphs. The new isomorphism test precisely reflects the structure of the directed edges. By identifying the isomorphic substructures of directed graphs, the hypergraph kernel for a pair of hypergraphs is computed by counting the number of pairwise isomorphic substructures from their directed line graphs. We show that our kernel limits tottering that arises in the existing walk and subtree based (hyper)graph kernels. Experiments on challenging (hyper)graph datasets demonstrate the effectiveness of our kernel.
Original languageEnglish
Title of host publicationProceedings of the 22nd International Conference on Pattern Recognition
PublisherIEEE Computer Society
Number of pages6
Publication statusAccepted/In press - 2014
Event22nd International Conference on Pattern Recognition - Stockholm, Sweden
Duration: 24 Aug 201428 Aug 2014

Conference

Conference22nd International Conference on Pattern Recognition
Country/TerritorySweden
CityStockholm
Period24/08/1428/08/14

Keywords

  • Support vector machines and kernel methods
  • Statistical, syntactic and structural pattern recognition
  • Machine learning and data mining

Cite this