Graph Homomorphism Convolution

Hoang Nguyen, Takanori Maehara
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:7306-7316, 2020.

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 $\mathcal{F}$-invariant) embedding maps which can be used for graph classification. Viewing the expressive power of a graph classifier by the $\mathcal{F}$-indistinguishable concept, we prove the universality property of graph homomorphism vectors in approximating $\mathcal{F}$-invariant functions. In practice, by choosing $\mathcal{F}$ whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-nguyen20c, title = {Graph Homomorphism Convolution}, author = {Nguyen, Hoang and Maehara, Takanori}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {7306--7316}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/nguyen20c/nguyen20c.pdf}, url = {https://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 $\mathcal{F}$-invariant) embedding maps which can be used for graph classification. Viewing the expressive power of a graph classifier by the $\mathcal{F}$-indistinguishable concept, we prove the universality property of graph homomorphism vectors in approximating $\mathcal{F}$-invariant functions. In practice, by choosing $\mathcal{F}$ whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.} }
Endnote
%0 Conference Paper %T Graph Homomorphism Convolution %A Hoang Nguyen %A Takanori Maehara %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-nguyen20c %I PMLR %P 7306--7316 %U https://proceedings.mlr.press/v119/nguyen20c.html %V 119 %X 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 $\mathcal{F}$-invariant) embedding maps which can be used for graph classification. Viewing the expressive power of a graph classifier by the $\mathcal{F}$-indistinguishable concept, we prove the universality property of graph homomorphism vectors in approximating $\mathcal{F}$-invariant functions. In practice, by choosing $\mathcal{F}$ whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.
APA
Nguyen, H. & Maehara, T.. (2020). Graph Homomorphism Convolution. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:7306-7316 Available from https://proceedings.mlr.press/v119/nguyen20c.html.

Related Material