Semantic Level of Detail for Knowledge Graphs: Discovering Abstraction Boundaries via Spectral Heat Diffusion

Edward Izgorodin

cs.LGMar 9, 2026

Semantic Level of Detail for Knowledge Graphs: Discovering Abstraction Boundaries via Spectral Heat Diffusion

Authors: Edward Izgorodin

Organizations: Mnemoverse.AI, Funchal, Madeira, Portugal

Abstract

Graph-structured knowledge systems -- from knowledge graphs to GraphRAG pipelines -- organize information into hierarchical communities, yet lack a principled mechanism for continuous resolution control: where do the qualitative boundaries between abstraction levels lie, and how should an agent navigate them? Current approaches rely on discrete community detection with manually tuned resolution parameters (e.g., Leiden $γ$ ), offering no continuous zoom and no formal guarantees. We introduce Semantic Level of Detail (SLoD), a framework that addresses both problems by defining a continuous zoom operator via heat kernel diffusion on a graph Laplacian whose kNN structure is induced by a Poincare-ball embedding. We prove hierarchical coherence in the tree limit (exact tree with Sarkar embedding), with bounded approximation error, and demonstrate consistent boundary-detection behaviour on noisy hierarchies; spectral gaps in the graph Laplacian then induce emergent scale boundaries -- scales where the representation undergoes qualitative transitions -- detectable without manual resolution tuning. On synthetic hierarchies (HSBM, 1024 nodes), spectral clustering at the BoundaryScan-detected scale recovers planted levels, with macro ARI saturating at 1.00 in the high-SNR regime (50-seed median) and meso ARI reaching 0.89 [0.86, 0.92] at r=200. On the full WordNet noun hierarchy (82K synsets), using 100 stratified leaf queries, detected boundaries align with true taxonomic depth ( $τ= 0.79$ ), demonstrating meaningful abstraction-level discovery in real-world knowledge graphs without resolution-parameter tuning. The composite weights, MAD threshold, and kNN-parameter rule ( $k = \max(10, \min(\lfloor\sqrt{N}\rfloor, 50))$ ) use defaults that transferred unchanged between HSBM and WordNet; their behaviour on graphs with implicit or qualitatively different hierarchical structure is open.

Figures & tables

Figure 1: Empirical anchor for Proposition 1 (i) on the kNN-of-Poincaré-embedding Laplacian (HSBM,

r{=}200

, seed 42, focus = node 0). The weight-divergence indicator

D_{w}(\sigma)=\JSD(\mathbf{w}(\sigma)\,\|\,\mathbf{w}(\sigma{+}\Delta\sigma))

exhibits two empirical features: a secondary local maximum near

\sigma\approx 1/\lambda_{2}\approx 128

(the macro Fiedler scale, where the gap ratio

\lambda_{3}/\lambda_{2}\approx 9.8

is large and Proposition 1 (i) predicts a peak), and a dominant peak in the mid-spectrum region near

1/\lambda_{20}

where many modes co-reorganise simultaneously. The meso scale

1/\lambda_{8}

does not produce a clean local maximum, consistent with the small gap there (

\lambda_{9}/\lambda_{8}\approx 1.5

, below the

R{=}2

threshold used in Algorithm 2 ); Proposition 1 (i)’s prediction is conditional on a large gap, and the meso level at this regime falls below that conditioning threshold.

$r$	20	40	60	80	100	150	200
ARI (macro, $K^{*}{=}2$ )	0.04	0.67	0.84	0.93	0.97	1.00	1.00
ARI (meso, $K^{*}{=}8$ )	0.09	0.15	0.24	0.43	0.63	0.79	0.91
ARI (micro, $K^{*}{=}64$ )	0.04	0.10	0.24	0.47	0.69	0.91	1.00

Table 1: Adjusted Rand Index at macro (

K^{*}{=}2

), meso (

K^{*}{=}8

), and micro (

K^{*}{=}64

) scales across signal-to-noise ratios. Numbers are from spectral clustering on the direct combinatorial graph Laplacian with

K_{\text{eigs}}{=}80

(sufficient to resolve the planted micro level); single seed (42), with multi-seed evidence in § 6.3 . The kNN-of-Poincaré-embedding default of § 6.3 reaches macro ARI

{=}0.42

r{=}20

(Table 3 ), so the low macro values here at

r{\leq}40

reflect the spectral-clustering baseline rather than SLoD itself (see takeaway (a) of § 6.3 ).

Figure 2: Effective dimensionality

K^{*}(\sigma)

vs. diffusion scale for varying signal strength

r

(left, log–log axes; planted levels

K{=}2,8,64

shown as horizontal dashed lines). At high

r

the trajectory sweeps through all three planted levels in order, with

\sigma

-separations equispaced on the log axis; at low

r

(

r{\leq}40

) the trajectory stops above

K{=}8

, signalling sub-Kesten–Stigum SNR. Right: smoothed

|dK^{*}/d\log\sigma|

(Savitzky–Golay window 11) as a diagnostic of effective-dimensionality changes (not the composite boundary score

S(\sigma)

of Algorithm 2 ); concentrates at scales where

K^{*}

crosses the planted levels (vertical reference lines for

r{=}200

K{=}8

and

K{=}2

are within

1.2\times

of each other in

\sigma

in the saturation regime, hence shown as a band.

Figure 3: Phase transition in boundary recovery. (a) ARI at macro and meso scales vs. $r$ (single seed=42); shaded region marks Kesten–Stigum threshold. (b) Spectral gap $\lambda_{3}/\lambda_{2}$ at $k{=}2$ on the direct combinatorial HSBM Laplacian vs $r$ — median across 10 seeds (42–51) with shaded interquartile range . The IQR widens at $r{=}60$ – $100$ , the regime where meso modes separate from the macro Fiedler value (high finite-size variance), then narrows for $r{\geq}100$ once the meso band stabilises above the macro–meso gap threshold ( $\lambda_{3}/\lambda_{2}{>}2$ ). The earlier single-seed (42) trajectory showed a spurious dip at $r{=}80$ that is now visibly an extreme of the IQR rather than a structural feature; macro recovery (panel a) was unaffected. (c) Theoretical signal-to-noise ratio; dashed line marks SNR $\,{=}\,1$ (Kesten–Stigum threshold; macro crosses at $r{\approx}40$ , meso at $r{\approx}100$ ).

Metric	Value	Interpretation
Kendall $\tau$	0.79 [0.75, 0.83]	strong ordering (bootstrap 95% CI)
Recall@1	0.56	56% of true depths detected $\pm$ 1 level
Recall@2	0.75	75% detected $\pm$ 2 levels
[email protected]	0.79	79% of detections near a true depth
Avg. peaks/node	3.9	$\sim$ 3–4 scale boundaries per leaf

Table 2: Experiment 2 metrics on full WordNet noun hierarchy (

N{=}82{,}115

Figure 4: Detected boundary scale $\sigma^{*}$ vs. true ancestor depth for 100 leaf nodes in WordNet ( $N{=}82{,}115$ ). Kendall $\tau=0.79$ confirms larger diffusion scales correspond to shallower ancestors.

Config	$r{=}20$	$r{=}40$	$r{=}60$	$r{=}80$	$r{=}100$	$r{=}150$	$r{=}200$
full (Poincaré)	0.42 [0.38, 0.47]	0.72 [0.70, 0.74]	0.85 [0.84, 0.86]	0.92 [0.91, 0.92]	0.95 [0.95, 0.96]	0.99 [0.99, 0.99]	1.00 [1.00, 1.00]
$V$ -only	0.42 [0.38, 0.47]	0.72 [0.70, 0.74]	0.85 [0.84, 0.86]	0.92 [0.91, 0.92]	0.95 [0.95, 0.96]	0.99 [0.99, 0.99]	1.00 [1.00, 1.00]
$D_{w}$ -only	0.40 [0.37, 0.45]	0.72 [0.70, 0.74]	0.85 [0.84, 0.86]	0.91 [0.91, 0.92]	0.95 [0.95, 0.96]	0.99 [0.99, 0.99]	1.00 [1.00, 1.00]
$C_{k}$ -only	0.42 [0.38, 0.46]	0.71 [0.69, 0.74]	0.85 [0.84, 0.86]	0.92 [0.91, 0.92]	0.95 [0.95, 0.96]	0.99 [0.99, 0.99]	1.00 [1.00, 1.00]
direct Laplacian	0.00 [0.00, 0.00]	0.00 [0.00, 0.68]	0.84 [0.83, 0.84]	0.91 [0.91, 0.92]	0.95 [0.95, 0.96]	0.99 [0.98, 0.99]	1.00 [1.00, 1.00]
full (Euclidean MDS)	0.44 [0.41, 0.46]	0.69 [0.67, 0.70]	0.81 [0.80, 0.82]	0.89 [0.88, 0.90]	0.93 [0.92, 0.93]	0.98 [0.98, 0.98]	1.00 [0.99, 1.00]

Table 3: Ablation: macro-scale ARI (

K^{*}{=}2

) on HSBM across

r\in\{20,40,60,80,100,150,200\}

N{=}1024

, planted 2

\times

\times

8 hierarchy. Cells are medians over 50 Poincaré-MDS seeds with bootstrap (BCa,

n{=}10{,}000

) 95% CIs; CIs are uncorrected for multiple comparisons across the

8\times 7

ablation grid. full (Euclidean MDS) swaps the embedding; full (binary kNN) strips Gaussian edge weights; full (random points) replaces the Poincaré coordinates with i.i.d. Gaussian noise while keeping the same Poincaré-kNN Laplacian (isolates the role of the points for the Fréchet mean step). direct Laplacian uses the combinatorial Laplacian of the HSBM graph instead of a kNN-of-embedding Laplacian (isolates the Laplacian construction).

Config	$r{=}20$	$r{=}40$	$r{=}60$	$r{=}80$	$r{=}100$	$r{=}150$	$r{=}200$
full (Poincaré)	0.08 [0.07, 0.09]	0.18 [0.17, 0.18]	0.33 [0.31, 0.35]	0.51 [0.48, 0.53]	0.61 [0.60, 0.66]	0.84 [0.80, 0.86]	0.89 [0.86, 0.92]
$V$ -only	0.08 [0.07, 0.09]	0.18 [0.17, 0.18]	0.33 [0.31, 0.35]	0.51 [0.48, 0.53]	0.61 [0.59, 0.65]	0.83 [0.78, 0.86]	0.88 [0.85, 0.90]
$D_{w}$ -only	0.08 [0.07, 0.09]	0.18 [0.17, 0.18]	0.33 [0.32, 0.35]	0.52 [0.49, 0.54]	0.62 [0.60, 0.66]	0.81 [0.77, 0.83]	0.84 [0.81, 0.88]
$C_{k}$ -only	0.09 [0.08, 0.10]	0.17 [0.17, 0.19]	0.32 [0.29, 0.36]	0.50 [0.47, 0.53]	0.64 [0.59, 0.66]	0.84 [0.81, 0.86]	0.86 [0.81, 0.89]
direct Laplacian	0.08 [0.06, 0.09]	0.16 [0.14, 0.17]	0.24 [0.21, 0.25]	0.37 [0.33, 0.40]	0.51 [0.47, 0.55]	0.68 [0.60, 0.74]	0.71 [0.67, 0.76]
full (Euclidean MDS)	0.08 [0.08, 0.08]	0.17 [0.16, 0.18]	0.32 [0.29, 0.33]	0.45 [0.43, 0.48]	0.57 [0.53, 0.60]	0.74 [0.71, 0.78]	0.81 [0.79, 0.83]

Table 4: Ablation: meso-scale ARI (

K^{*}{=}8

) on HSBM across

r\in\{20,40,60,80,100,150,200\}

N{=}1024

, planted 2

\times

\times

8 hierarchy. Cells are medians over 50 Poincaré-MDS seeds with bootstrap (BCa,

n{=}10{,}000

) 95% CIs; CIs are uncorrected for multiple comparisons across the

8\times 7

Figure 5: Composite-score profiles $S(\sigma)$ at $r{=}200$ , seed 42, with the top-scoring peak of each configuration marked. (a) Indicator ablation under Poincaré embedding (single seed=42): $V$ -only and the full composite share a dominant peak at $\sigma^{*}\!\approx\!7$ , while $D_{w}$ -only has a distinct earlier peak at $\sigma^{*}\!\approx\!2$ . $C_{k}$ -only at this seed coincides with the $V$ -only peak; the multi-seed median analysis in takeaway (e) shows $C_{k}$ -only’s typical peak is later ( $\sigma^{*}\!\approx\!14.9$ ). The direct-Laplacian variant picks a late $\sigma^{*}\!\approx\!36$ on a different Laplacian spectrum. (b) Geometry comparison for the full composite: the Euclidean-MDS Laplacian has a useful scale range more than an order of magnitude lower than the Poincaré one, consistent with takeaway (b).

Figure 6: BoundaryScan scaling on HSBM with a fixed $2{\times}4{\times}8$ hierarchy and $K_{\mathrm{eigs}}{=}50$ . Left: wall-clock scan time, log–log slope $0.77$ (the sub-linear trend at small $N$ is constant-overhead-dominated). Right: peak Python allocation (measured via tracemalloc ), log–log slope $0.98$ . Both consistent with $O(NK_{\mathrm{eigs}}^{2})$ time and $O(NK_{\mathrm{eigs}})$ memory (Lanczos partial eigendecomposition) for fixed $K_{\mathrm{eigs}}$ .

Knowledge Graphs

Knowledge graphs represent entities and relationships as structured, queryable networks for integrating data and supporting reasoning.

See all 232 papers

May 22, 2026

SeedER: Seed-Expand-Retrieve for Efficient Knowledge Graph Retrieval

Knowledge graphs (KGs) offer a rich representation for relational knowledge, but their irregular structure makes retrieval challenging: ego-graph expansion grows rapidly, and dense embedding methods struggle with multi-hop compositional queries. Several approaches use LLM agents to explore the KG, analyze candidate nodes, and decide where to explore next. While expressive, these approaches can incur substantial computational and memory costs. On the other hand, we show theoretically that dense embeddings precomputed for graph nodes, even with augmented structure and neighborhood-aware features, can require embedding dimensions comparable to the size of the graph to answer families of knowledge graph queries. This limitation can be overcome with query-adaptive embeddings under certain conditions, and there are graph neural network (GNN) variants that can do so. However, processing the whole graph with a GNN can also incur substantial memory and computational costs, and it requires dense ground-truth labels indicating whether each node answers the query. Straightforward

k

-hop selection around anchor nodes can also be problematic: small

k

limits the nodes we can see, and even with small

k

values such as three and four, the

k

-hop subgraph can grow substantially. In this work, we devise a new approach using Graph Transformers and reinforcement learning that is much less demanding in memory and computation, can run on a CPU at inference time as a first-stage retriever, and requires feedback on only a small number of nodes at a time during training. We show that this method is competitive with methods that fine-tune LLMs to retrieve information from KGs. We call our method SeedER (Seed-Expand-Retrieve), and position it primarily as a first-stage retriever that can run with modest computational resources.

Hamed Shirzad, Frederik Wenkel, Dominique Beaini +2

Valence Labs, Montréal, QC, Canada · Recursion, Salt Lake City, UT, USA · University of British Columbia, Department of Computer Science, Vancouver, BC, Canada

Graph-Based Retrieval Knowledge Graph Question Answering Multi-Hop Reasoning

Ask PDF

Oct 17, 2026

Uncovering Semantic Hierarchies in Text-Attributed Graphs via Variational EM-based LLM-GNN Synergy

While hierarchical structures are intrinsic to organizing human knowledge, current representation learning on text-attributed graphs predominantly operates on flat semantic spaces, overlooking the rich coarse-to-fine granularity inherent in real-world data. To bridge this gap, we propose SHiFT, which synergizes the reasoning power of LLMs with the structural representation capability of GNNs within an Expectation-Maximization (EM) paradigm. In the E-step, we harness LLMs as expert taxonomists to induce an explicit semantic tree, introducing a lightweight Mapping & Diagnosis strategy that reduces inference costs by surgically updating the hierarchy only when anomalies are detected. In the M-step, we align the GNN encoder with this induced hierarchy from complementary perspectives, including clustering partition, topological skeleton, and semantic concepts. Theoretical analysis interprets SHiFT as a generalized Variational EM algorithm. Extensive experiments demonstrate that SHiFT not only achieves state-of-the-art performance but also uncovers high-quality, human-readable taxonomies. Our code can be found at https://github.com/Cloudy1225/SHiFT.

Yunhui Liu, Xudong Jin, Qizhuo Xie +5

State Key Laboratory for Novel Software Technology, Nanjing University · Department of Statistics, University of Wisconsin–Madison · National Engineering Laboratory for Big Data Analysis and Applications, Peking University

Text-Attributed Graph Learning Hierarchical Representation Learning Taxonomy Induction LLMs for Graph Learning

Ask PDF

Mar 5, 2026

Core-based Hierarchies for Efficient GraphRAG

Retrieval-Augmented Generation (RAG) enhances large language models by incorporating external knowledge. However, existing vector-based methods often fail on global sensemaking tasks that require reasoning across many documents. GraphRAG addresses this by organizing documents into a knowledge graph with hierarchical communities that can be recursively summarized. Current GraphRAG approaches rely on Leiden clustering for community detection, but we prove that on sparse knowledge graphs, where average degree is constant and most nodes have low degree, modularity optimization admits exponentially many near-optimal partitions, making Leiden-based communities inherently non-reproducible. To address this, we propose replacing Leiden with k-core decomposition, which yields a deterministic, density-aware hierarchy in linear time. We introduce a set of lightweight heuristics that leverage the k-core hierarchy to construct size-bounded, connectivity-preserving communities for retrieval and summarization, along with a token-budget-aware sampling strategy that reduces LLM costs. We evaluate our methods on real-world datasets including financial earnings transcripts, news articles, and podcasts, using three LLMs for answer generation and five independent LLM judges for head-to-head evaluation. Across datasets and models, our approach consistently improves answer comprehensiveness and diversity while reducing token usage, demonstrating that k-core-based GraphRAG is an effective and efficient framework for global sensemaking.

Jakir Hossain, Ahmet Erdem Sarıyüce

University at Buffalo Buffalo, NY, USA · Amazon Web Services. This publication describes work performed at University at Buffalo, and is not associated with Amazon Web Services.

Graph Retrieval-Augmented Generation Graph-Based Retrieval Graph Clustering

Ask PDF

Abstract

Knowledge Graphs

Explore similar work

SeedER: Seed-Expand-Retrieve for Efficient Knowledge Graph Retrieval

Uncovering Semantic Hierarchies in Text-Attributed Graphs via Variational EM-based LLM-GNN Synergy

Core-based Hierarchies for Efficient GraphRAG