Gur Lifshitz

Shiri Chechik, Gur Lifshitz, Doron Mukhtar

This paper advances the state of the art in girth approximation within the CONGEST model. Manoharan and Ramachandran [PODC '24] provided the first significant improvement in girth approximation in over a decade. We build on this momentum and make progress on all fronts: we provide a unified family of algorithms yielding girth approximation-round tradeoffs for undirected networks; we obtain improved bounds for directed networks; and we establish better lower bounds for directed and undirected weighted networks. Together, these results substantially narrow the remaining complexity gaps across all settings. Specifically, for networks with $n$ nodes and hop-diameter $D$, we show that one can compute, with high probability: $(1)$ An $f$-approximation for unweighted undirected girth in $\tilde{O}(n^{1/f}+D)$ rounds, for every constant integer $f>2$, $(2)$ A $(2k-1+o(1))$-approximation for weighted undirected girth in $\tilde{O}(n^{(k+1)/(2k+1)}+D)$ rounds, for every constant integer $k>1$, and $(3)$ A $2$-approximation for directed unweighted girth, and a $(2+\varepsilon)$-approximation for directed weighted girth, both in $\tilde{O}(n^{2/3}+D)$ rounds. We also prove new lower bounds for directed networks and for undirected weighted networks: for every integer $k > 2$ and $\varepsilon>0$, assuming the Erdős-Simonovits' even cycle conjecture (and unconditionally for $k\in\{3,4,6\}$), any $(k-\varepsilon)$-approximation for the girth requires $\tildeΩ(n^{k/(2k-1)})$ rounds, even when $D = O(\log n)$.

Snir Hordan, Maya Bechler-Speicher, Gur Lifshitz et al.

Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non-isomorphic graphs. One popular example is the usage of graph Laplacian eigenvectors for positional encoding in MPNNs and Graph Transformers. The expressive power of such Spectrally-enhanced GNNs (SGNNs) is usually evaluated via the k-WL graph isomorphism test hierarchy and homomorphism counting. Yet, these frameworks align poorly with the graph spectra, yielding limited insight into SGNNs' expressive power. We leverage a well-studied paradigm of classifying graphs by their largest eigenvalue multiplicity to introduce an expressivity hierarchy for SGNNs. We then prove that many SGNNs are incomplete even on graphs with distinct eigenvalues. To mitigate this deficiency, we adapt rotation equivariant neural networks to the graph spectra setting to propose a method to provably improve SGNNs' expressivity on simple spectrum graphs. We empirically verify our theoretical claims via an image classification experiment on the MNIST Superpixel dataset and eigenvector canonicalization on graphs from ZINC.