When a phone or vehicle sends semantic messages, it transmits compressed meaning instead of raw bits. That only works if the receiving base station holds the background knowledge needed to interpret the message. Current knowledge-aware association methods, which decide which base station each user connects to, reduce that knowledge to a single number: an overlap ratio, or a probability that the right knowledge base is present. We propose a different test. Model each base station's knowledge as a piece of a shared knowledge graph, meaning a network of entities joined by typed relations. Then ask whether that piece contains the specific multi-hop chain of relations the user's task needs. Base stations advertise a compact summary of which relation chains they can complete. Users are assigned by combining that summary with channel quality. Every assignment comes with a concrete path through the station's graph that justifies it.
This matters because the scalar view fails in a predictable way. Two nodes can share most of their entities yet lack the one bridging relation a query needs, while a weaker-signal station with less overlap may hold exactly that bridge. The path view also solves a second problem. Operators get an auditable reason for why a user was sent away from the strongest signal, instead of a converged Lagrange multiplier.
Core Claim
Our claim has two parts. First, whether a semantic message will be decoded at a base station is predicted much better by path closure than by entity or knowledge-base overlap. Path closure means the station's subgraph contains a grounded instance of a relation sequence the task requires. Second, a signature of a few kilobytes per station is enough to get most of the benefit of perfect knowledge of every station's graph. That signature lists the relation-type sequences the station can complete, with counts.
The first part is what makes the idea worth doing. The second part is what makes it more than "run breadth-first search on everything." The explanation comes for free, because the chosen relation sequence and one of its grounded paths at the chosen station form a certificate that anyone can check.
Where This Sits
The association side supplies the optimization skeleton and the throughput metric. Joint User Association and Bandwidth Allocation in Semantic Communication Networks measures throughput in messages per second and maps channel capacity to message throughput. It handles uncertain knowledge through a chance constraint that requires a target semantic confidence level. We keep this formulation and replace its scalar knowledge-matching probability with a path-closure probability.
The hybrid semantic/bit networks work, Wireless Resource Optimization in Hybrid Semantic/Bit Communication Networks, constrains the design. It shows that under low knowledge matching, semantic coding delay outweighs compression gains, so the system must fall back to bits. Our association must therefore price a bit fallback explicitly and not assume semantics always wins. The vehicular work (xURLLC-Aware Service Provisioning in Vehicular Networks, Knowledge Base Aware Semantic Communication in Vehicular Networks) pairs senders and receivers over a library of 12 discrete knowledge bases with Zipf-distributed popularity. Like the other association papers, it treats a knowledge base as an opaque unit and never inspects its relational structure. That is precisely the simplification we remove.
Graph-enhanced semantic communication motivates the knowledge-graph representation but stops at a single link. Semantic Communication Enhanced by Knowledge Graph Representation Learning transmits knowledge graphs through a language-model-plus-graph-network encoder, assuming a pre-shared knowledge base. Reliable Semantic Communication System Enabled by Knowledge Graph and Explainable Semantic Communication for Text Tasks transmit filtered, isolated triplets. None of the three does multi-cell association, and none reasons over multi-hop paths.
The graph-explainability side supplies the method in three roles:
- Path policy. MINERVA learns, by reinforcement learning, a policy that walks relations from a query entity. We reuse its trained policy on the global graph as a predictor of which relation sequences a query type tends to need, rather than as an online answer-finder.
- Grounding a certificate. TransferNet propagates entity scores along attended relations. It gives a differentiable way to ground a relation sequence in a station's subgraph and return the highest-scoring path.
- Honest judging. Reasoning on Knowledge Graphs with Debate Dynamics blocks its judge from entity embeddings so that decisions rest only on paths. We copy this for our certificate checker.
- Evaluating explanations. Generating and Evaluating Plausible Explanations for Knowledge Graph Completion separates faithful from plausible explanations. We use its human-verification protocol.
Research Program
Setting. A global knowledge graph is split across base stations, so each station holds a subgraph. A user's task carries a query: a head entity and a target relation. Semantic decoding at station $b$ succeeds if $b$'s subgraph contains a path from the head entity to the correct answer whose relation sequence $\pi$ is one the reasoning model can use.
Predicting needed paths. A path policy trained on the global graph gives $p(\pi \mid q)$, the probability that query type $q$ is answered through relation sequence $\pi$, with length up to three hops.
Station signatures. Each station advertises $S_b$, the set of relation sequences it can ground, with counts of grounded instances. This can be computed offline by relation-matrix products restricted to the subgraph and truncated to the top few hundred sequences.
Closure probability. The predicted probability that station $b$ closes query $q$ is
$$c_{q,b} = \sum_{\pi \in S_b} p(\pi \mid q)\, g(n_{b,\pi}),$$
where $n_{b,\pi}$ is the number of grounded instances of $\pi$ at $b$, and $g$ is a calibrated saturating function learned from held-out queries. We learn $g$ because a single instance may not touch the user's specific head entity.
Association. We substitute $c_{q,b}$ for the scalar knowledge-matching probability in the chance-constrained association of Joint User Association and Bandwidth Allocation. A user whose best closure probability falls below the confidence level is assigned under the bit-fallback cost from the hybrid tandem-queue model.
Certificates. After assignment, the station grounds the top relation sequence for the actual head entity and returns the path as the certificate. If grounding fails, that failure is itself logged evidence that the signature mispredicted.
Mobility. For vehicular scenarios we test signature staleness. Signatures are refreshed every $T$ seconds while subgraphs change as roadside units cache new knowledge. This addresses the static-snapshot limitation the vehicular papers acknowledge.
Baselines
Max-SINR. The naive reference assigns each user to the strongest-signal station and falls back to bit transmission on semantic failure. It uses the same channel realizations, the same bandwidth, and the same fallback cost model as our method. It needs no tuning.
Scalar knowledge-matching association. The strongest existing method is the joint association and bandwidth allocation of Joint User Association and Bandwidth Allocation in Semantic Communication Networks, using its chance-constrained formulation for imperfect matching. Here the knowledge-matching degree is computed from entity overlap between the query's neighborhood and the station's subgraph. It is the strongest competitor because it already optimizes the same message-throughput objective with the same solver family. The only difference is the knowledge signal, so any gain isolates our ingredient. Its reported result is an average of 42.5 kmsg/s in the perfect-matching case on Europarl, about 14% above max-SINR. That number is for sentence transmission, not partitioned knowledge graphs. We found no reported result on Lacuna for any association method on a partitioned-knowledge-graph task. We will therefore re-run it, giving both methods an identical solver, the same confidence level sweep (55% to 95%), and the same hyperparameter budget for the overlap threshold that we give to $g$.
Knowledge-First Pairing. From the vehicular papers, this ranks stations by knowledge-base popularity match. It is run in the six-lane freeway simulation with our subgraphs standing in for their knowledge bases.
Dense embedding similarity. This assigns users by cosine similarity between a MiniLM embedding of the query and a mean embedding of each station's subgraph triplets. It is fed into the same chance constraint after calibration on the same held-out split.
Oracle breadth-first search. This upper bound gives the association solver the full subgraph of every station and checks exact closure per query. It defines how much of the achievable gain the compact signature recovers. We also report the signaling bytes this oracle would require.
Ablations. We run the signature with counts removed (presence only), the signature restricted to one-hop relations, and the signature with a uniform $p(\pi \mid q)$ in place of the learned path policy. Beating the scalar baseline means higher task-success rate and message throughput at matched confidence, with at most comparable fallback rate, on partitions where overlap and closure are not trivially correlated.
Why not just…?
Why not just use max-SINR and fetch missing knowledge over the backhaul? The hybrid-network results in Wireless Resource Optimization in Hybrid Semantic/Bit Communication Networks show that mismatched semantics push delay into the coding queue. The vehicular papers report roughly 1 ms latency penalties from bit fallback, which matter under low-latency deadlines. However, backhaul fetch costs were not modeled there. We include a max-SINR plus fetch baseline with backhaul latency swept from 1 to 20 ms. If fast backhaul erases our gain, we will report the crossover latency as the regime boundary rather than claim a general win.
Why not just use entity overlap or embedding similarity? This is the main threat, since it is cheap and may correlate with closure on naturally clustered partitions. The multi-hop results of TransferNet and MINERVA suggest that answers depend on specific edges, not on aggregate overlap. That is suggestive, not proof, for association. We settle it with two partition families. Natural partitions are clustered by entity community. Adversarial partitions deliberately separate bridge relations from high-overlap stations. If overlap matches our method on natural partitions, we will say the gain is confined to bridge-sparse deployments.
Why not just run exact search on each station's graph? It is exact, and we treat it as the oracle. It requires either shipping every subgraph to the association controller or querying every candidate station per user. Our contribution only stands if the signature recovers most of the oracle's task success at orders of magnitude less signaling. We measure that tradeoff directly.
Why not explain a neural association policy post hoc? In the GradPath study, human verification accuracy on Kinship was 34.78% with gradient-influence explanations versus 83.33% with paths. The debate-dynamics work shows why embedding access has to be blocked to prevent shortcut decisions. We test this in our own setting with the human study below.
Proposed Experiments
Testbed. We partition NELL-995, WN18RR, CoDEx and MetaQA across 7 to 19 base stations under the three partition families. Queries come from the benchmarks' test splits. The wireless layer uses the message-throughput transformation and chance-constrained model of the joint association paper. The vehicular setting reuses the six-lane freeway simulation with 60 vehicles and roadside-unit caching.
Metrics. We report task success (Hits@1 at the serving station), message throughput, end-to-end delay, fallback rate, and signaling bytes per station. We also report certificate validity: the fraction of certificates that ground correctly and that an embedding-blocked judge accepts.
Decisive checks. The first is the correlation between predicted closure $c_{q,b}$ and actual decoding success, compared with that of overlap and embedding similarity. If path closure is not a clearly better predictor on at least the adversarial partitions, the idea fails. The second is the fraction of oracle task success recovered versus signature size. The third is a signature-staleness sweep under mobility.
Human study. Following the GradPath protocol, network-literate participants judge whether an assignment away from the strongest station was correct. They see either our path certificate or the scalar overlap with dual variables. We measure accuracy and decision time. Accuracy with our certificate should be clearly higher than with scalar overlap plus dual variables. Achieving this requires the certificate to be faithful, not merely plausible, which the grounding check verifies.
References
- Joint User Association and Bandwidth Allocation in Semantic Communication Networks
- Wireless Resource Optimization in Hybrid Semantic/Bit Communication Networks
- xURLLC-Aware Service Provisioning in Vehicular Networks: A Semantic Communication Perspective
- Knowledge Base Aware Semantic Communication in Vehicular Networks
- Semantic Communication Enhanced by Knowledge Graph Representation Learning
- Reliable Semantic Communication System Enabled by Knowledge Graph
- Explainable Semantic Communication for Text Tasks
- Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning
- TransferNet: An Effective and Transparent Framework for Multi-hop Question Answering over Relation Graph
- Reasoning on Knowledge Graphs with Debate Dynamics
- Generating and Evaluating Plausible Explanations for Knowledge Graph Completion