Home >

news Help

Publication Information


Title
Japanese: 
English:Graph Homomorphism Convolution 
Author
Japanese: Hoang Nguyen, 前原 貴憲.  
English: Hoang Nguyen, Takanori Maehara.  
Language English 
Journal/Book name
Japanese: 
English:Proceedings of Machine Learning Research: 
Volume, Number, Page Vol. 119       
Published date June 13, 2020 
Publisher
Japanese: 
English:PMLR 
Conference name
Japanese: 
English:37th International Conference on Machine Learning 
Conference site
Japanese: 
English: 
Official URL http://proceedings.mlr.press/v119/nguyen20c.html
 
Abstract In this paper, we study the graph classification problem from the graph homomorphism perspective. We consider the homomorphisms from F to G, where G is a graph of interest (e.g. molecules or social networks) and F belongs to some family of graphs (e.g. paths or non-isomorphic trees). We show that graph homomorphism numbers provide a natural invariant (isomorphism invariant and F-invariant) embedding maps which can be used for graph classification. Viewing the expressive power of a graph classifier by the F-indistinguishable concept, we prove the universality property of graph homomorphism vectors in approximating F-invariant functions. In practice, by choosing F whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.

©2007 Tokyo Institute of Technology All rights reserved.