An edge-based matching kernel for graphs through the directed line graphs

Lu Bai, Zhihong Zhang, Chaoyan Wang, Edwin R. Hancock

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

In this paper, we propose a new edge-based matching kernel for graphs. We commence by transforming a graph into a directed line graph. The reasons of using the line graph structure are twofold. First, for a graph, its directed line graph is a dual representation and each vertex of the line graph represents a corresponding edge in the original graph. As a result, we can develop an edge-based matching kernel for graphs by aligning the vertices in their directed line graphs. Second, the directed line graph may expose richer graph characteristics than the original graph. For a pair of graphs, we compute the h-layer depth-based representations rooted at the vertices of their directed line graphs, i.e., we compute the depth-based representations for edges of the original graphs through their directed line graphs. Based on the new representations, we define an edge-based matching method for the pair of graphs by aligning the h-layer depth-based representations computed through the directed line graphs. The new edge-based matching kernel is thus computed by counting the number of matched vertices identified by the matching method on the directed line graphs. Experiments on standard graph datasets demonstrate the effectiveness of our new edge-based matching kernel.

Original languageEnglish
Title of host publicationComputer Analysis of Images and Patterns - 16th International Conference, CAIP 2015, Proceedings
EditorsGeorge Azzopardi, Nicolai Petkov
PublisherSpringer Verlag
Pages85-95
Number of pages11
ISBN (Print)9783319231167
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event16th International Conference on Computer Analysis of Images and Patterns, CAIP 2015 - Valletta, Malta
Duration: 2 Sep 20154 Sep 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9257
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Computer Analysis of Images and Patterns, CAIP 2015
Country/TerritoryMalta
CityValletta
Period2/09/154/09/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'An edge-based matching kernel for graphs through the directed line graphs'. Together they form a unique fingerprint.

Cite this