The most accurate neural systems for answering logical queries over incomplete knowledge graphs cannot run on large graphs. A query of this kind looks like "which drugs target a protein that interacts with gene X but not with gene Y." The strongest of these systems is GNN-QE. For every constant in the query it runs a full pass of relational message passing over the whole graph, and message passing means each node repeatedly updates itself from its neighbours. On the 2-million-node WikiKG-QE benchmark this cost is prohibitive, so only a weaker, tokenization-based model scales (Inductive Logical Query Answering in Knowledge Graphs). Database research solved an analogous problem for shortest paths with hub labeling. Each node stores a short list of distances to a few "hub" nodes, and any distance can be recovered by combining two such lists. Separately, workload-aware partitioning showed that the queries users actually ask are a better guide to data layout than graph topology alone (Partout: a distributed engine for efficient RDF processing).
This proposal brings the two ideas into neural query answering. We precompute learned path representations from a small set of hubs, choose those hubs and the relations they serve from a query log, and at query time run exact message passing only on a small neighbourhood around each query constant. Composing through hubs averages many paths together, so hub-mediated signals tend to wash out the differences between nearby candidate answers. This is the over-smoothing problem, and we counter it with a query-conditioned high-pass correction. Put in two sentences: offline, compute path summaries from workload-chosen hubs; at query time, compute only the short path from each anchor to its nearby hubs and glue the two halves together, keeping the part of the hub signal that tells neighbouring candidates apart.
Core Claim
GNN-QE's projection step computes, for anchor entity $a$ and relation $r$, a representation $h_r(a,v)$ for every candidate $v$. It does this with a generalized Bellman-Ford recursion, which aggregates over all paths from $a$ to $v$. We claim this quantity admits a hub-factorized approximation:
$$ \tilde h_r(a,v) = h^{\text{loc}}_r(a,v) + z_r(a)\,\Big(m_r(a,v) - \tfrac{1}{|F(v)|}\textstyle\sum_{u\in F(v)} m_r(a,u)\Big),\qquad m_r(a,v)=\bigoplus_{c\in H(a)} h^{\text{loc}}_r(a,c)\otimes L_r(c,v). $$
The symbols are as follows. $h^{\text{loc}}_r$ is exact message passing restricted to a $k$-hop neighbourhood of $a$. $H(a)$ is the set of hubs reached inside that neighbourhood. $L_r(c,v)$ is a stored, pruned label: the representation of paths from hub $c$ to $v$ under relation $r$, computed offline. $\oplus$ and $\otimes$ are the learned aggregation and composition operators of the NBFNet-style network. $F(v)$ is the local neighbourhood of $v$. $z_r(a)\in[0,1]$ is a gate computed from the query relation and the anchor-to-hub scores.
The bracketed term is the diversification idea of Complete the Missing Half applied to the hub pathway. Subtracting the fringe mean removes the component of the hub signal that all nearby candidates share, which is exactly the component that over-smoothing inflates.
What is new is threefold. First, we compose learned path representations through a hub cover rather than running global propagation. Second, both the hubs and the relations for which labels are stored are chosen from the query workload rather than from degree. Third, the anti-smoothing correction is conditioned on the query rather than fixed per node.
Research Program
Prior work that supplies the method. Bridging Indexing Structure and Graph Learning via Core-Fringe (CFGNN) already imports hub labeling into GNNs. It routes messages fringe-to-core and back, with a 2-hop path-coverage guarantee, and trains on a single consumer GPU. Our proposal differs from CFGNN in three respects. CFGNN picks its core from static topology, performs no logical query answering, and does nothing about homogenization at the core.
Prior work that motivates the workload-driven choice. Partout mines SPARQL query logs into fragments and reports beating the 2-hop partitioning scheme HAR+ often by an order of magnitude on BTC 2008 (Partout: a distributed engine for efficient RDF processing). Mining frequent patterns from query logs similarly doubled throughput over min-cut partitioning (Query Workload-based RDF Graph Fragmentation and Allocation). Both are symbolic engines that place data. We instead use the log to decide which learned labels to materialize.
Prior work that constrains the design. The disjunction result in Query2box warns that compressing many answers into one compact geometric object requires dimension growing with entity count. We therefore never compress; each hub label keeps a pruned, per-node sparse list. CLMPT shows that restricting updates to variable nodes saves only up to 9.6% GPU memory, which suggests that sharper local tricks will not close the gap to web scale.
The work has three parts, described in order below.
Hub election. We treat hub election as a budgeted coverage problem. Hubs are the nodes that most often appear on high-scoring anchor-to-answer paths of logged queries, weighted by query frequency. Labels are stored only for (hub, relation) pairs whose frequency clears a threshold. Unseen relations fall back to purely local propagation. A per-hub top-$K$ pruning of $L_r(c,\cdot)$ bounds memory at roughly $|H|\cdot|R_{\text{freq}}|\cdot K\cdot d$, where $d$ is the embedding width. We report this footprint explicitly.
Training. We train end to end on the standard query types, with labels recomputed periodically from the current network weights. Because gradients through $L_r$ would require full-graph passes, we first stop gradients through the stored labels. We then test whether occasional refresh closes the gap to full backpropagation on the small benchmarks, where full training is feasible.
Measuring smoothing directly. We measure smoothing on candidate representations as the ratio of within-fringe to across-fringe variance of $\tilde h_r(a,\cdot)$. We follow the caution in Are we measuring oversmoothing in graph neural networks correctly? and report more than one measure rather than trusting a single similarity score.
CLQA benchmarks ship no query logs. We therefore build workloads by sampling benchmark query structures with Zipf-skewed anchors and relations. We also build drifted test workloads in which the skew is permuted. This is an honest limitation: the workload is synthetic, and the drift experiment below is our check on whether the method overfits to it.
Baselines
Full GNN-QE. The naive reference is GNN-QE run exactly as released in the DeepGraphLearning/InductiveQE code on graphs where it fits: the FB15k-237-derived inductive splits of Inductive Logical Query Answering in Knowledge Graphs. It is the accuracy ceiling our approximation must approach. It runs on the same GPU, with its published hyperparameters and an equal tuning budget of trials for our variant. Retaining at least 95% of its hard-answer mean reciprocal rank (MRR) while cutting per-query peak memory by an order of magnitude counts as success.
NodePiece-QE. The strongest existing method that actually runs at WikiKG-QE scale is NodePiece-QE with CQD-Beam from the same paper. The file records only that it scales to 2 million nodes and 11 million edges while GNN-QE cannot. No reported MRR result was found on Lacuna for NodePiece-QE on WikiKG-QE, so we will rerun it from the released code on identical query splits. Beating it means higher hard-answer MRR and Hits@10 on WikiKG-QE at comparable per-query latency.
Anchor-local truncated propagation. This isolates whether hubs matter at all. It is GNN-QE restricted to a personalized-random-walk neighbourhood of each anchor with the same node budget as ours, in the spirit of the truncated walks of Sarkar et al..
Degree-selected hubs. This CFGNN-style ablation isolates the workload ingredient. It uses identical label memory but elects hubs by degree or centrality.
Gate and correction ablations. One variant removes the fringe-mean correction. A second replaces our query-conditioned gate with a node-only gate built from center–neighbour similarity, as in ALaGCN (When Do GNNs Work). Every variant receives the same training steps and hyperparameter trials.
Why not just…?
Why not just truncate GNN-QE to a neighbourhood around each anchor? This is the most serious threat. If answers to benchmark queries lie mostly within a few hops of the anchors, truncation will match us for free. The anchor-local baseline at matched node budget settles it. We will report results stratified by anchor-to-answer distance. The hub method should win specifically on answers beyond the truncation radius. If it does not win there, the hub machinery is unjustified and we will say so.
Why not just use NodePiece-QE, which already scales? It scales because it drops end-to-end relational message passing, and the inductive paper reports that GNN-QE is the more accurate model where both run. Whether that accuracy gap persists at 2 million nodes is unknown, since GNN-QE never ran there. Our WikiKG-QE comparison measures the gap directly, and a small or zero gap would sink the proposal.
Why not just pick hubs by degree, as CFGNN does? Degree hubs are cheap and need no log. Partout's gains over topology-based partitioning suggest workload matters for symbolic queries, but that evidence does not transfer automatically to learned labels. The degree-hub ablation at equal memory is the test. So is the drift experiment, where workload-chosen hubs could plausibly do worse than degree hubs.
Why not just keep message passing shallow to avoid smoothing? Chain queries of three hops and intersections of multi-hop branches need paths longer than one or two hops. Hub composition is precisely a way to obtain long paths without deep stacks. What remains open is whether the smoothing correction matters at all once depth is removed, and the correction-removal ablation answers that.
Proposed Experiments
We evaluate the standard query types, including negation, on the inductive FB15k-237 splits, where full GNN-QE provides ground truth for the approximation error of $\tilde h$. We also evaluate on WikiKG-QE, where only the approximate methods run. Metrics are filtered hard-answer MRR and Hits@10, per-query latency, peak GPU memory, and offline label storage and build time. Beyond headline accuracy, three checks decide the proposal:
- On the small graphs, the correlation between approximation error and answer distance, which tells us whether hubs actually recover long paths.
- The drifted-workload evaluation. The method should degrade gracefully toward the local fallback, not below the anchor-local baseline.
- The smoothing ratio with and without the fringe-mean correction. Removing the correction should both collapse within-fringe variance and hurt MRR most on queries routed through high-degree hubs.
If all three hold and WikiKG-QE accuracy exceeds NodePiece-QE, the claim stands. If truncation alone matches us, we will report a negative result for hub composition.
References
- Inductive Logical Query Answering in Knowledge Graphs
- Partout: a distributed engine for efficient RDF processing
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Bridging Indexing Structure and Graph Learning: Expressive and Scalable Graph Neural Network via Core-Fringe
- Query Workload-based RDF Graph Fragmentation and Allocation
- Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings
- Conditional Logical Message Passing Transformer for Complex Query Answering
- Are we measuring oversmoothing in graph neural networks correctly?
- A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs
- When Do GNNs Work: Understanding and Improving Neighborhood Aggregation