Graph Homomorphism Convolution
This provides a theoretical foundation for graph classification methods, applicable to domains like molecules or social networks, but is incremental in building on existing homomorphism concepts.
The paper tackles the graph classification problem by using graph homomorphism numbers as invariant embeddings, proving their universality in approximating invariant functions and showing efficiency for bounded tree-width families.
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.