Graph Homomorphism Convolution

• URL: http://arxiv.org/abs/2005.01214v2
• Date: Thu, 2 Jul 2020 01:10:37 GMT
• Title: Graph Homomorphism Convolution
• Authors: Hoang NT, Takanori Maehara
• Abstract summary: We show that graph homomorphism numbers provide a natural invariant (isomorphism invariant and $mathcalF$-invariant) embedding maps which can be used for graph classification. By choosing $mathcalF$ whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.
• Score: 19.94778871237204
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• Graph Automorphism Group Equivariant Neural Networks [1.9643748953805935]
  Permutation equivariant neural networks are typically used to learn from data that lives on a graph. We show how to construct neural networks that are equivariant to Aut$(G)$ by obtaining a full characterisation of the learnable, linear, Aut$(G)$-equivariant functions.
  arXiv  Detail & Related papers  (2023-07-15T14:19:42Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Expectation-Complete Graph Representations with Homomorphisms [5.939858158928473]
  We are interested in efficient alternatives that become arbitrarily expressive with increasing resources. Our approach is based on Lov'asz' characterisation of graph isomorphism through an infinite dimensional vector of homomorphism counts.
  arXiv  Detail & Related papers  (2023-06-09T12:12:07Z)
• Probing Graph Representations [77.7361299039905]
  We use a probing framework to quantify the amount of meaningful information captured in graph representations. Our findings on molecular datasets show the potential of probing for understanding the inductive biases of graph-based models. We advocate for probing as a useful diagnostic tool for evaluating graph-based models.
  arXiv  Detail & Related papers  (2023-03-07T14:58:18Z)
• Quantum isomorphism of graphs from association schemes [0.0]
  We show that any two Hadamard graphs on the same number of vertices are quantum isomorphic. This follows from a more general recipe for showing quantum isomorphism of graphs arising from certain association schemes.
  arXiv  Detail & Related papers  (2022-09-10T03:22:28Z)
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
  A graph can be represented as a point set in enough dimensions using a simplex embedding and sampling. The isomorphism of them corresponds to the existence of a perfect registration between the point set forms of the graphs. The related idea of equivalence classes suggests that graph canonization may be an important tool in tackling graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-11-15T12:16:21Z)
• Relative stability toward diffeomorphisms in deep nets indicates performance [66.51503682738931]
  We show that stability toward diffeomorphisms does not strongly correlate to performance on benchmark data sets of images. We find that the stability toward diffeomorphisms relative to that of generic transformations $R_f$ correlates remarkably with the test error $epsilon_t$. For CIFAR10 and 15 known architectures, we find $epsilon_tapprox 0.2sqrtR_f$, suggesting that obtaining a small $R_f$ is important to achieve good performance.
  arXiv  Detail & Related papers  (2021-05-06T07:03:30Z)
• Learning on heterogeneous graphs using high-order relations [37.64632406923687]
  We propose an approach for learning on heterogeneous graphs without using meta-paths. We decompose a heterogeneous graph into different homogeneous relation-type graphs, which are then combined to create higher-order relation-type representations.
  arXiv  Detail & Related papers  (2021-03-29T12:02:47Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.