Home > Research > Publications & Outputs > Expectation-Complete Graph Representations with...

Research

Electronic data

  • 2306.05838v2

    Final published version, 299 KB, PDF document

    Available under license: CC BY-SA: Creative Commons Attribution-ShareAlike 4.0 International License

Links

Keywords

View graph of relations

Expectation-Complete Graph Representations with Homomorphisms

Research output: Working paper › Preprint

Published

Standard

Expectation-Complete Graph Representations with Homomorphisms. / Welke, Pascal; Thiessen, Maximilian; Jogl, Fabian et al.
Arxiv, 2023.

Research output: Working paper › Preprint

Harvard

Welke, P, Thiessen, M, Jogl, F & Gärtner, T 2023 'Expectation-Complete Graph Representations with Homomorphisms' Arxiv. <https://arxiv.org/abs/2306.05838v2>

APA

Welke, P., Thiessen, M., Jogl, F., & Gärtner, T. (2023). Expectation-Complete Graph Representations with Homomorphisms. Arxiv. https://arxiv.org/abs/2306.05838v2

Vancouver

Welke P, Thiessen M, Jogl F, Gärtner T. Expectation-Complete Graph Representations with Homomorphisms. Arxiv. 2023 Jun 9.

Author

Welke, Pascal ; Thiessen, Maximilian ; Jogl, Fabian et al. / Expectation-Complete Graph Representations with Homomorphisms. Arxiv, 2023.

Bibtex

@techreport{4b46af7a23664f73a88c617cc7beab76,
title = "Expectation-Complete Graph Representations with Homomorphisms",
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\'asz' characterisation of graph isomorphism through an infinite dimensional vector of homomorphism counts. Our empirical evaluation shows competitive results on several benchmark graph learning tasks. ",
keywords = "cs.LG, cs.DS",
author = "Pascal Welke and Maximilian Thiessen and Fabian Jogl and Thomas G{\"a}rtner",
note = "accepted for publication at ICML 2023",
year = "2023",
month = jun,
day = "9",
language = "English",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

RIS

TY - UNPB

T1 - Expectation-Complete Graph Representations with Homomorphisms

AU - Welke, Pascal

AU - Thiessen, Maximilian

AU - Jogl, Fabian

AU - Gärtner, Thomas

N1 - accepted for publication at ICML 2023

PY - 2023/6/9

Y1 - 2023/6/9

N2 - 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\'asz' characterisation of graph isomorphism through an infinite dimensional vector of homomorphism counts. Our empirical evaluation shows competitive results on several benchmark graph learning tasks.

AB - 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\'asz' characterisation of graph isomorphism through an infinite dimensional vector of homomorphism counts. Our empirical evaluation shows competitive results on several benchmark graph learning tasks.

KW - cs.LG

KW - cs.DS

M3 - Preprint

BT - Expectation-Complete Graph Representations with Homomorphisms

PB - Arxiv

ER -