Research map / Graph learning / GNN architectures

Expressive Power of Deep Homomorphism Networks over Relational Databases

NeurIPS 2026 · Graph learning › GNN architectures · approach: Substructure-aware GNN expressivity · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Characterizes the expressive power of deep homomorphism networks (DHNs) over relational databases via logics (UNFO, UNFOC, HML, GHML, RHML, UQAFO, EML, HML+C), and derives decidability results for emptiness and subsumption, with small synthetic experiments on local transitivity and the sun property.

Problem

Precise expressive power of deep homomorphism networks used as vertex classifiers over relational databases, and decidability of static analysis (emptiness, subsumption) for DHNs with different aggregations.

Approach

Relates max-, sum-, and mean-aggregation DHNs to logical fragments (UNFO, UNFOC, GHML, RHML, UQAFO, HML+C) and to deep embedding networks, obtaining exact characterizations for max and partial ones for sum, and uses these to prove decidability/undecidability of static analysis problems.

Key results

• On local transitivity, sum-aggregation DHN reaches F1 0.98 and AUROC 1.00, versus 0.83/0.93 for max-aggregation DHN and 0.94/0.98 for GIN.
• On the sun property, sum-aggregation DHN achieves F1 1.00 and AUROC 1.00, versus 0.88/0.94 for GIN with homomorphism counts.
• Max-aggregation DHNs are shown to be exactly equivalent to UNFO and HML; sum-aggregation DHNs on bounded-degree databases with connected patterns match UNFOC/GHML; emptiness and subsumption for sum-DHNs are undecidable.

Surprising findings

• GIN performs remarkably well on local transitivity, close to the sum-DHN.
• Even properties in FO can be inexpressible in UNFOC, so connected sum-DHNs exceed UNFOC on unrestricted-degree databases.

Limitations

• Exact logical characterization of sum- and mean-aggregation DHNs on unrestricted-degree databases remains open.
• Decidability of max-DHN emptiness/subsumption complexity is open.
• Experiments are proof-of-concept on small synthetic datasets.

Experimental setup

Datasets: synthetic local transitivity graphs synthetic sun property graphs

Benchmarks: synthetic local transitivity dataset synthetic sun property dataset

Metrics: F1 AUROC

Baselines: GCN GraphSAGE GIN GIN with hom. counts

Builds on: Deep Homomorphism Networks UNFO graded modal logic Lovász homomorphism count theorem Barceló et al. GNNs with homomorphism counts

Closest papers by meaning

• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.87)
• Deep Homomorphism Networks (NeurIPS 2024 · similarity 0.86)
• Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization (NeurIPS 2025 · similarity 0.86)
• Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.86)
• Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.85)
• Weisfeiler-Leman at the margin: When more expressivity matters (ICML 2024 · similarity 0.85)