Paper Abstract and Keywords |
Presentation |
2015-11-26 15:00
[Poster Presentation]
Halting in Random Walk Kernels Mahito Sugiyama (Osaka Univ.), Karsten Borgwardt (ETHZ) IBISML2015-63 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
Random walk kernels measure graph similarity by counting matching walks in two graphs. In their most popular form of geometric random walk kernels, longer walks of length $k$ are downweighted by a factor of $lambda^k$ ($lambda < 1$) to ensure convergence of the corresponding geometric series. We know from the field of link prediction that this downweighting often leads to a phenomenon referred to as halting: Longer walks are downweighted so much that the similarity score is completely dominated by the comparison of walks of length 1. This is a na{"i}ve kernel between edges and vertices. We theoretically show that halting may occur in geometric random walk kernels. We also empirically quantify its impact in simulated datasets and popular graph classification benchmark datasets. Our findings promise to be instrumental in future graph kernel development and applications of random walk kernels. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
Graph kernel / Random walk kernel / Halting / / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 115, no. 323, IBISML2015-63, pp. 75-82, Nov. 2015. |
Paper # |
IBISML2015-63 |
Date of Issue |
2015-11-19 (IBISML) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
IBISML2015-63 |
Conference Information |
Committee |
IBISML |
Conference Date |
2015-11-25 - 2015-11-27 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Epochal Tsukuba |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
Information-Based Induction Science Workshop (IBIS2015) |
Paper Information |
Registration To |
IBISML |
Conference Code |
2015-11-IBISML |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Halting in Random Walk Kernels |
Sub Title (in English) |
|
Keyword(1) |
Graph kernel |
Keyword(2) |
Random walk kernel |
Keyword(3) |
Halting |
Keyword(4) |
|
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Mahito Sugiyama |
1st Author's Affiliation |
Osaka University (Osaka Univ.) |
2nd Author's Name |
Karsten Borgwardt |
2nd Author's Affiliation |
ETH Zurich (ETHZ) |
3rd Author's Name |
|
3rd Author's Affiliation |
() |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2015-11-26 15:00:00 |
Presentation Time |
180 minutes |
Registration for |
IBISML |
Paper # |
IBISML2015-63 |
Volume (vol) |
vol.115 |
Number (no) |
no.323 |
Page |
pp.75-82 |
#Pages |
8 |
Date of Issue |
2015-11-19 (IBISML) |