It is proved that sufficiently parameterized RGNNs contain sparse subnetworks that maintain 1-RWL expressivity and derive a lower bound on the probability that a random pruning yields such a subnetwork.
Abstract
Graph neural networks (GNNs) are widely used, but how parameter sparsity affects the expressivity of relational (RGNNs) and temporal (TGNNs) variants is poorly understood. The Strong Expressive Lottery Ticket Hypothesis (SELTH) posits the existence of sparse GNNs that preserve Weisfeiler-Leman (WL) expressivity on static graphs. We generalize this existence result to a probabilistic statement for multi-relational and temporal domains via the relational WL (RWL). We prove that sufficiently parameterized RGNNs contain sparse subnetworks that maintain 1-RWL expressivity and derive a lower bound on the probability that a random pruning yields such a subnetwork. We show that common TGNNs and cross-graph message passing schemes admit RGNN reformulations such that they inherit these guarantees and, moreover, that the expressivity of a sparse RGNN is connected to its optimization behavior under common update regimes. Experiments instantiate the bound, compare it to empirical probabilities on synthetic data, and study how pre-training expressivity relates to optimization and prediction quality metrics on temporal and molecular benchmarks.
FICE (Fully Inductive Cardinality Estimation), the first learned cardinality estimator for BGP queries over KGs that generalizes to entirely unseen graphs (including unseen relations), without any retraining is presented.
Tim Schwabe, Lukas Ketzer, Maribel Acosta· arXiv.org· 0 citations
Experiments show that RelShap produces explanations that are more faithful to the data-generating process, correctly identifying the dominant feature in controlled settings where existing methods, including Conditional SHAP and ManifoldShap, do not.
Seungeun Lee, João Fonseca, Julia Stoyanovich· 0 citations
Experiments on four benchmarks for node classification and link prediction show that PriDyG consistently outperforms geometrically decaying baselines under the same privacy budget and matches the utility of naive per-update retraining while reducing cumulative privacy cost by up to three orders of magnitude.
FlowNeg is introduced, a context-conditioned hierarchical generative flow network that amortizes reward-proportional sampling without normalizing a composite reward over the entity set: given a positive triple and corruption side, it selects a type, then an entity.
Predictive analytics increasingly runs over structures that grow without bound, such as logistics networks, digital twins, and knowledge graphs, where queries carry hard latency budgets yet the deployed guarantees are only statistical. We develop a worst-case alternative from computable model theory. We model the evolving structure as a Gandy direct limit, the limit of a chain generated by a fixed-point operator rather than by Fraïssé amalgamation, and prove the Gandy direct-limit theorem: if a polynomially computable chain is generated by such an operator, every operation returns the canonical code of its value, and a functional boundary condition holds, then membership, predicates, operations, and equality are all decidable in polynomial time. The countable atomless Boolean algebra and the unit-free Ershov algebra are presented this way. The applied payoff is an operator-generated logistics network—the universal envelope of all admissible consolidations, which subsumes any particular deployment rather than recording one—on which every bounded prediction is decidable in time polynomial in the queried code, with a degree fixed by the query rather than the horizon. Here prediction means an emergence or reachability decision against a deterministic generator, not statistical forecasting; probabilistic rules add a provable confidence floor. A reproducible simulation on synthetic instances confirms this cost model: the work a bounded query does is polynomial in the length of its input—the code that names the target—and does not grow with the size of the network.
A. Nechesov, Vadim Puzarenko· IEEE Access· 0 citations
Constructing special graphs is an important task within graph theory and computer science. Many popular graph constructions are the result of a comprehensive exploration of relevant graphs and human ingenuity. Given the rise of generative AI usage in mathematics, it is natural to test whether LLMs are able to construct graphs with specified properties using their reasoning capabilities. Unfortunately, many natural graph construction problems, such as finding extremal Ramsey-good graphs (i.e., avoiding specific monochromatic subgraphs), have been explored extensively in the literature, making it difficult to ascertain whether a construction is the product of an LLM's reasoning capabilities or its recollection from training data. In this work, we introduce \textbf{RamseyGadgets}, a novel dataset of 70 underexplored graph construction problems that require finding Ramsey-good graphs with special properties (e.g., containing an edge with a fixed color). These problems have reasonably sized solutions (at most 10 vertices) that can be verified by SAT solvers, making them suitable for automatic evaluation. Our dataset is easily expandable, as one can simply change the monochromatic subgraphs being avoided to obtain a new set of problems. We evaluate the performance of five open-source LLMs on our dataset and report the results. Our findings show that LLMs achieve only 37.70% accuracy on the hard-tier problems in our dataset, with Gemma-4-31B achieving the highest performance out of the five. We also showcase how our dataset allows us to ascertain what kind of hints help LLMs perform better at this task.
Zohair Raza Hassan, Deepak Pandita· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
