Expectation-Complete Graph Representations with Homomorphisms

Pascal Welke, Maximilian Thiessen, Fabian Jogl, Thomas Gärtner
6/9/2023
cs.LGcs.DS

No official code found. Best implementation: pwelke/homcount (3 stars, MIT, last commit 2025-02-21).

Abstract

We investigate novel random graph embeddings that can be computed in expected polynomial time and that are able to distinguish all non-isomorphic graphs in expectation. Previous graph embeddings have limited expressiveness and either cannot distinguish all graphs or cannot be computed efficiently for every graph. To be able to approximate arbitrary functions on graphs, we are interested in efficient alternatives that become arbitrarily expressive with increasing resources. Our approach is based on Lovász' characterisation of graph isomorphism through an infinite dimensional vector of homomorphism counts. Our empirical evaluation shows competitive results on several benchmark graph learning tasks.

View on arXivView PDF

Code Implementations(1)

pwelke/homcountCommunity100%
MIT

Expectation-Complete Graph Representations

30PythonMay 27, 20231 years agoMIT

Similar Papers

Structural Node Embeddings with Homomorphism Counts

84% match2023

Creating generalizable downstream graph models with random projections

82% match2023

Homomorphism distortion: A metric to distinguish them all and in the latent space bind them

81% match2025

Homomorphism Counts for Graph Neural Networks: All About That Basis

80% match1 repo32026

Homomorphism Counts for Graph Neural Networks: All About That Basis

80% match1 repo32024

PlanE: Representation Learning over Planar Graphs

80% match1 repo132023

Cite this paper

@article{welke2023expectationcomplete,
  title  = {Expectation-Complete Graph Representations with Homomorphisms},
  author = {Pascal Welke and Maximilian Thiessen and Fabian Jogl and Thomas Gärtner},
  year   = {2023},
  eprint = {2306.05838},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2306.05838v2},
  journal = {ICML 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2306.05838.svg)](https://codeofpaper.com/paper/2306.05838)

Discussion