Timezone: »

 
Spotlight
KONG: Kernels for ordered-neighborhood graphs
Moez Draief · Konstantin Kutzkov · Kevin Scaman · Milan Vojnovic

Thu Dec 06 06:50 AM -- 06:55 AM (PST) @ Room 220 CD
in Thu Track 1 -- Session 1 »

We present novel graph kernels for graphs with node and edge labels that have ordered neighborhoods, i.e. when neighbor nodes follow an order. Graphs with ordered neighborhoods are a natural data representation for evolving graphs where edges are created over time, which induces an order. Combining convolutional subgraph kernels and string kernels, we design new scalable algorithms for generation of explicit graph feature maps using sketching techniques. We obtain precise bounds for the approximation accuracy and computational complexity of the proposed approaches and demonstrate their applicability on real datasets. In particular, our experiments demonstrate that neighborhood ordering results in more informative features. For the special case of general graphs, i.e. graphs without ordered neighborhoods, the new graph kernels yield efficient and simple algorithms for the comparison of label distributions between graphs.

Author Information

Moez Draief (Noah's Ark Labs, Huawei Research)
Konstantin Kutzkov (London School of Economics)
Kevin Scaman (Noah's Ark Lab, Huawei Technologies)
Milan Vojnovic (London School of Economics (LSE))

Milan Vojnovic is Professor, Chair in Data Science, with the Department of Statistics, at London School of Economics and Political Science (LSE), where he is also director of MSc in Data Science program. Prior to this, he worked for 13 years in a corporate research laboratory environment, from 2004 until 2016, as a researcher with Microsoft Research, Cambridge, United Kingdom. He received his Ph.D. degree in Technical Sciences from Ecole Polytechnique Federale de Lausanne (EPFL), Switzerland, in 2003, and both M.Sc. and B.Sc. degrees in Electrical Engineering from the University of Split, Croatia, in 1995 and 1998, respectively. He undertook an internship with Mathematical Research Center, Bell Laboratories, Murray Hill, New Jersey, in 2001. From 2005 to 2014, he was a visiting professor with the University of Split, Croatia, and from 2014 to 2016, he was an affiliated lecturer with the Statistical Laboratory, at the University of Cambridge.    His research interests are in data science, machine learning, artificial intelligence, game theory, multi-agent systems, and information networks, with applications in the broad area of information systems and networks. He has made contributions to the theory and the design of computation platforms for processing large-scale data, and to the performance evaluation of computer systems and networks, in particular, in the areas of incentives and online services, distributed computing, network resource allocation, transport control protocols, and peer-to-peer networks.   He received several prizes for his work. In 2010, he was awarded the ACM Sigmetrics Rising Star Researcher award, and, in 2005, the ERCIM Cor Baayen Award. He received the IEEE IWQoS 2007 Best Student Paper Award (with Shao Liu and Dinan Gunawardena), the IEEE Infocom 2005 Best Paper Award (with Jean-Yves Le Boudec), the ACM Sigmetrics 2005 Best Paper Award (with Laurent Massoulie), and the ITC 2001 Best Student Paper Award (with Jean-Yves Le Boudec).   He delivered numerous lectures and seminars in both academia and industry. He taught several editions of a computer networking course within the undergraduate computer science program at the University of Split. He taught two editions of a course on contest theory within Part III of Mathematical Tripos (master program in mathematics) at the University of Cambridge. He authored the book “Contest Theory: Incentive Mechanisms and Ranking Methods,” Cambridge University Press, 2016.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors