Zobrazeno 1 - 10
of 7 647
pro vyhledávání: '"P, Leman"'
We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any circuit must have depth super-linear or even super-polynomial in the number of variables, far exceeding the linear w
Externí odkaz:
http://arxiv.org/abs/2411.14267
Autor:
Zhou, Junru, Zhang, Muhan
The ability of graph neural networks (GNNs) to count homomorphisms has recently been proposed as a practical and fine-grained measure of their expressive power. Although several existing works have investigated the homomorphism counting power of cert
Externí odkaz:
http://arxiv.org/abs/2410.03517
Autor:
Wu, Yulai, Ponomarenko, Ilia
A circulant graph is a Cayley graph of a finite cyclic group. The Weisfeiler-Leman-dimension of a circulant graph $X$ with respect to the class of all circulant graphs is the smallest positive integer~$m$ such that the $m$-dimensional Weisfeiler-Lema
Externí odkaz:
http://arxiv.org/abs/2406.15822
Autor:
Müller, Luis, Morris, Christopher
Graph neural network architectures aligned with the $k$-dimensional Weisfeiler--Leman ($k$-WL) hierarchy offer theoretically well-understood expressive power. However, these architectures often fail to deliver state-of-the-art predictive performance
Externí odkaz:
http://arxiv.org/abs/2406.03148
The Weisfeiler-Leman dimension of a graph $G$ is the least number $k$ such that the $k$-dimensional Weisfeiler-Leman algorithm distinguishes $G$ from every other non-isomorphic graph. The dimension is a standard measure of the descriptive complexity
Externí odkaz:
http://arxiv.org/abs/2402.11531
We introduce $r$-loopy Weisfeiler-Leman ($r$-$\ell{}$WL), a novel hierarchy of graph isomorphism tests and a corresponding GNN framework, $r$-$\ell{}$MPNN, that can count cycles up to length $r + 2$. Most notably, we show that $r$-$\ell{}$WL can coun
Externí odkaz:
http://arxiv.org/abs/2403.13749
Autor:
Schneider, Thomas, Schweitzer, Pascal
The Weisfeiler-Leman (WL) dimension is a standard measure in descriptive complexity theory for the structural complexity of a graph. We prove that the WL-dimension of a graph on $n$ vertices is at most $3/20 \cdot n + o(n)= 0.15 \cdot n + o(n)$. The
Externí odkaz:
http://arxiv.org/abs/2403.12581
The Weisfeiler-Leman algorithm ($1$-WL) is a well-studied heuristic for the graph isomorphism problem. Recently, the algorithm has played a prominent role in understanding the expressive power of message-passing graph neural networks (MPNNs) and bein
Externí odkaz:
http://arxiv.org/abs/2402.07568
Autor:
Kiefer, Sandra, Neuen, Daniel
The Weisfeiler-Leman (WL) dimension is an established measure for the inherent descriptive complexity of graphs and relational structures. It corresponds to the number of variables that are needed and sufficient to define the object of interest in a
Externí odkaz:
http://arxiv.org/abs/2402.03274
The $k$-Weisfeiler-Leman ($k$-WL) graph isomorphism test hierarchy is a common method for assessing the expressive power of graph neural networks (GNNs). Recently, GNNs whose expressive power is equivalent to the $2$-WL test were proven to be univers
Externí odkaz:
http://arxiv.org/abs/2402.02484