TY - GEN
T1 - An edge-based matching kernel for graphs through the directed line graphs
AU - Bai, Lu
AU - Zhang, Zhihong
AU - Wang, Chaoyan
AU - Hancock, Edwin R.
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84945981052&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-23117-4_8
DO - 10.1007/978-3-319-23117-4_8
M3 - Conference contribution
AN - SCOPUS:84945981052
SN - 9783319231167
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 85
EP - 95
BT - Computer Analysis of Images and Patterns - 16th International Conference, CAIP 2015, Proceedings
A2 - Azzopardi, George
A2 - Petkov, Nicolai
PB - Springer Verlag
T2 - 16th International Conference on Computer Analysis of Images and Patterns, CAIP 2015
Y2 - 2 September 2015 through 4 September 2015
ER -