Spectral Initialization and Scheduled Graph Smoothness for Uncertain Knowledge Graph Completion

Spectral Initialization and Scheduled Graph Smoothness for Uncertain Knowledge Graph Completion Md Abrar Jahin1 , Taufikur Rahman Fuad2 , Jay Pujara1 , Craig A. Knoblock1

arXiv:2609.02519v1 [cs.LG] 2 Sep 2026

1

University of Southern California 2 Islamic University of Technology jahin@usc.edu, taufikur@iut-dhaka.edu, jpujara@usc.edu, knoblock@isi.edu

Abstract Uncertain knowledge graphs (UKGs) extend knowledge graphs by assigning each triple a continuous confidence score. Since most possible triples lack observed confidences, recent methods rely on semi-supervised learning to generate pseudolabels. These methods initialize entity embeddings without using the confidence-weighted graph, discarding its global community and hub structure. We introduce QUEST, which adds no trainable parameters to the standard confidencedistribution learning pipeline. First, QUEST initializes entity embeddings using the smallest non-trivial eigenvectors of the confidence-weighted graph Laplacian, incorporating community and hub structure before training. Second, QUEST applies an unbiased mini-batch Dirichlet energy regularizer to enforce early-stage structural consistency. On two UKG datasets, QUEST improves confidence prediction and link prediction on six of eight metric–dataset pairs over prior methods and matches the previous best on the remaining two, while removing the instability spike observed on dense graphs. These results indicate that spectral structural priors combined with a graph Dirichlet energy regularizer improve accuracy, training stability, and checkpoint reliability in UKG completion.

Introduction Real-world Knowledge Graphs (KGs) are fundamental for data representation and automated reasoning, but their construction naturally introduces noise and varying degrees of certainty. To capture this ambiguity, Uncertain Knowledge Graphs (UKGs) annotate each relational triple with a continuous confidence score. Modeling uncertainty in KGs is necessary as embeddings are systematically uncalibrated, which reduces their reliability in downstream reasoning tasks (Tabacof and Costabello 2020). UKG completion aims to infer missing facts with their confidence levels. Because most possible triples lack observed confidences, recent works formulate UKG completion as a semi-supervised learning problem (Chen, Yeh, and Kuo 2021; Wu et al. 2025). Foundational UKG completion methods adapt deterministic scoring functions to regress or bound confidence scores. UKGE (Chen et al. 2019) maps bilinear scores to confidence values through hand-designed transformations, while BEUrRE (Chen et al. 2021) models uncertainty through geometric box-intersection volumes. To address label sparsity, PASSLEAF (Chen, Yeh, and Kuo 2021) introduces a poolbased semi-supervised framework, and UPGAT (Tseng et al.

2023) extends graph attention to UKGs. The state-of-theart framework, ssCDL (Wu et al. 2025), models confidence as a distribution over discrete bins and introduces a metalearning stage that generates pseudo-labels for unobserved triples. Despite these advances, existing methods randomly initialize entity embeddings and process triples locally. By lifting discrete entities into a continuous vector space without structural priors, they discard the global community and hub topology. This structural disconnect affects optimization stability and representational quality. In deterministic KGs, spectral methods and graph-smoothness regularization have long been used to encode community structure (Ng, Jordan, and Weiss 2001; Kipf and Welling 2017; Zhou et al. 2021). However, these ideas have not been transferred to the uncertain setting. Recent studies on self-training further show that topology-agnostic pseudo-labeling propagates errors through the graph (Wang et al. 2023; Liu et al. 2026). In UKG completion, meta-learning modules assign pseudoconfidence labels to uniformly corrupted entity pairs. Without a structural prior, the smoothness objective pulls entity pairs together while the ranking gradient for corrupted triples pushes them apart. On dense graphs, this gradient conflict induces training instability and causes sharp error spikes. We address this disconnect with QUEST, a drop-in extension of ssCDL that introduces two parameter-free interventions. First, QUEST initializes entity embeddings using the k smallest non-trivial eigenvectors of the confidenceweighted graph Laplacian. This spectral initialization places entities from the same high-confidence communities near each other and centers high-degree hubs, grounding the embeddings in global topology before training begins. Second, QUEST imposes an unbiased mini-batch graph-smoothness regularizer derived from Dirichlet energy (Zhou et al. 2021; Li et al. 2024b). We find that this regularizer conflicts with meta-learned self-training on dense graphs. QUEST therefore uses a scheduling strategy that deactivates the smoothness penalty exactly when pseudo-labeling begins, yielding to meta-learned supervision while preserving the spectral prior. Our main contributions are: (i) We identify a structural disconnect in UKG completion and analyze the gradient conflict between graph-smoothness regularization and uniform entity corruption. (ii) We propose a spectral initialization method

with no additional trainable parameters that embeds global community and hub structure from the confidence-weighted graph Laplacian into the initial entity representations. (iii) We formulate an unbiased mini-batch graph Dirichlet energy regularizer that enforces topological smoothness during early-stage confidence distribution learning, preserving structural integrity before self-training.

Related Work Uncertain knowledge graph completion. Foundational UKG embedding models adapt deterministic scoring functions. UKGE (Chen et al. 2019) introduces UKGElogi and UKGErect that map bilinear scores to confidence values through logistic and rectified linear transformations, respectively. These hand-designed mappings produce point estimates and cannot capture distributional uncertainty. BEUrRE (Chen et al. 2021) represents entities as axis-aligned hyperrectangles and relations as affine maps, estimating confidence through box-intersection volumes. These computations scale with embedding dimension, increasing complexity. PASSLEAF (Chen, Yeh, and Kuo 2021) integrates multiple scoring functions with a semi-supervised sample pool to mitigate label sparsity, yet still treats triples independently without exploiting graph topology. UPGAT (Tseng et al. 2023) constructs an attention graph from predicted Knowledge Graph Embedding (KGE) scores rather than observed confidence weights, weakening the supervisory signal from annotated certainty values. UKGsE (Yang et al. 2022) combines embedding-based inference with an approximate logical framework but optimizes entity vectors without graph-smoothness constraints, allowing entities in the same high-confidence cluster to drift apart. Probabilistic entity representations have also been proposed for multi-hop KG reasoning (Choudhary et al. 2021). Universal orthogonal parameterization further generalizes KGE models (Li et al. 2024a), while spectral clustering has been used to select anchor entities before propagation (Liang et al. 2024). KGE models are systematically uncalibrated, reducing reliability in downstream tasks (Tabacof and Costabello 2020). Neighborhood-intervention consistency has been proposed as a post-hoc confidence measure for KGE predictions (Wang, Liu, and Sheng 2021). ssCDL (Wu et al. 2025) models confidence as a full distribution and couples it with PCDG, a MAML-style (Finn, Abbeel, and Levine 2017) meta-training stage that generates pseudoconfidence labels. Despite state-of-the-art results, ssCDL, like prior UKG methods, randomly initializes entity embeddings and uses graph structure only through triple corruption, discarding the global community and hub topology encoded in the confidence-weighted graph. Semi-supervised and pseudo-confidence learning for UKGs. UKG completion is inherently semi-supervised because most triples lack observed confidences. Self-training and pseudo-labeling are used in graph representation learning to propagate supervision to unlabeled nodes (Liu et al. 2026; Wang et al. 2023), while meta-learning approaches have been developed for few-shot semi-supervised learning (Ding et al. 2022). In the UKG setting, ssCDL’s PCDG

stage (Wu et al. 2025) is the first to integrate metalearning into pseudo-confidence generation. A dedicated meta-network produces soft targets for uniformly corrupted entity pairs and updates them through a one-step metagradient. Noisy pseudo-labels propagate errors through graph and degrade performance as label noise increases (Wang et al. 2023). Topology-agnostic pseudo-label selection underperforms structure-aware alternatives (Liu et al. 2026). Structure-sensitive node selection outperforms uniform strategies in self-training (Wang et al. 2025). PCDG suffers from the same issue: uniformly corrupting entities ignores structural distance in the confidence-weighted graph. When a corrupted entity lies far from the original, the resulting pseudo-label opposes graph smoothness and introduces gradient interference. Structural priors and spectral methods for KGE. In deterministic KGs, structure-aware architectures like CompGCN (Vashishth et al. 2020) and relational GCNs propagate information along typed edges, but they assume binary truth values and require graph access at inference time. Spectral methods provide a parameter-free alternative. Graph Laplacian eigenvectors encode community and hub structure and have been used for spectral clustering (Ng, Jordan, and Weiss 2001), positional encodings, and GNN pre-training (Dai et al. 2025). Graph convolution has been derived as a first-order approximation of spectral filtering through a normalized Laplacian (Kipf and Welling 2017), though this idea remained confined to GNNs rather than embedding-based completion. Recent work exploits spectral structure through attention mechanisms (Chen, O’Bray, and Borgwardt 2022), graphsmoothness unrolling (Do et al. 2024), and graph-based structural priors (Sani 2026), but these approaches add trainable components and complexity. In contrast, QUEST initializes embeddings from the k smallest non-trivial eigenvectors of the confidence-weighted Laplacian, placing entities from the same communities near each other and positioning bridging hubs at structural centers without additional parameters or pre-training. Graph smoothness and regularization. Regularizing embeddings to be smooth over a graph is classically formulated as minimizing the Dirichlet energy. In the GNN literature, Dirichlet energy has been used to prevent oversmoothing in deep networks (Zhou et al. 2021), support joint graph learning and data imputation (Xu et al. 2023; Zhang et al. 2024), and extend Laplacian regularization to negative weights (Li et al. 2024b). Label-smoothness regularization has also been applied to KG-aware recommendation (Wang et al. 2019), though these methods assume binary interaction labels and do not directly transfer to continuous UKG confidence values. Spectral regularization can also interfere with adaptive graph training when not carefully balanced (You et al. 2023). Existing methods keep the regularizer active throughout training. QUEST differs in three ways: it regularizes entity embeddings through confidence-weighted Laplacian without GNN, estimates regularizer through unbiased mini-batch sampling, and deactivates when PCDG begins. This schedul-

Figure 1: Overall architecture of QUEST ing avoids gradient conflict between pseudo-label training and graph smoothness on dense graphs.

Background and Preliminaries Uncertain Knowledge Graphs A UKG is a tuple G = (V, R, E), where V is a set of entities, R a set of relation types, and E ⊆ V × R × V × (0, 1] is a set of confidence-annotated triples (h, r, t, s). Each triple states that relation r holds between head entity h and tail entity t with confidence s ∈ (0, 1]. We study two tasks. Confidence prediction takes a query triple (h, r, t) and predicts its confidence s; performance is measured by Mean Squared Error (MSE) and Mean Absolute Error (MAE). Link prediction takes a query pair (h, r, ·) and ranks candidate tail entities t′ ∈ V; performance is measured by confidence-weighted mean reciprocal rank (WMRR) and Hits@1 in the filtered setting (Chen et al. 2019). We let n = |V|, d denote the embedding dimension, and B = 101 the number of confidence bins. ssCDL backbone. QUEST builds on ssCDL (Wu et al. 2025), which jointly learns confidence prediction and link prediction over uncertain triples. For each triple (h, r, t), ssCDL learns entity and relation embeddings and constructs the feature vector ϕ(h, r, t) = [eh ∥ er ∥ et ] ∈ R3d . A confidence distribution learner maps this feature vector to a categorical distribution over B = 101 confidence bins in [0, 1], trained against a truncated Gaussian target centered at the observed confidence score s. The final predicted confidence ŝ(h, r, t) is obtained as the expected bin value and normalized to [0.1, 1.0]. In parallel, ssCDL uses a second scoring network for link prediction, optimized with a confidence-weighted margin

ranking loss over negatively corrupted triples. The confidence prediction loss and ranking loss are combined using Kendall uncertainty weighting (Kendall, Gal, and Cipolla 2018), yielding the joint objective Lcdl =

Lcp Lrl + log σ1 + + log σ2 , 2σ12 20σ22

where σ1 and σ2 are learnable task uncertainty parameters.

QUEST We propose QUEST, an extension of ssCDL (Wu et al. 2025) with two parameter-free additions targeting a weakness in UKG completion: the loss of structure once entities are lifted into embeddings. First, entity embeddings are initialized from the k smallest non-trivial eigenvectors of the confidence-weighted graphPLaplacian L = D − A, where P Aij = r sijr and Dii = j Aij . This encodes community structure and hub topology at initialization. Second, QUEST adds a graph-smoothness regularizer Lsmooth to the CDLRL objective, penalizing high-confidence neighbors that drift apart early in training. A stability analysis shows this regularizer conflicts with PCDG on dense graphs. QUEST therefore deactivates Lsmooth once PCDG begins at epoch 30, leaving spectral initialization as the structural prior. Figure 1 summarizes the pipeline.

Confidence-Weighted Graph Laplacian We construct a confidence-weighted undirected graph over V from training triples. For each ordered pair (i, j) ∈ V 2 , the edge weight aggregates the confidence of triples linking i, j in either direction: X Aij = s (1) r: (i,r,j,s)∈E or (j,r,i,s)∈E

Thus, A is symmetric. Treating directed KG edges as undirected is standard in structural KGE methods (Vashishth et al. 2020). The degree matrix is D = diag(A1), and the unnormalized graph Laplacian is L = D−A

(2)

Because A is symmetric and non-negative, L is symmetric positive semi-definite with real eigenvalues 0 = λ1 ≤ λ2 ≤ · · · ≤ λn . The smallest eigenvalue λ1 = 0 corresponds to the √ constant eigenvector 1/ n and is discarded. The remaining eigenvectors v2 , . . . , vn , ordered by increasing eigenvalue, form the graph spectral basis: small eigenvalues correspond to smooth community-scale signals, while large eigenvalues correspond to local high-frequency variations.

Spectral Entity Initialization Algorithm. Let d be the embedding dimension. We compute the k = d smallest non-trivial eigenvectors of the Tikhonovregularized Laplacian Lε = L + εI,

−5

ε = 10

(3)

using the ARPACK shift-invert method (shift σ0 = 0, tolerance 10−4 , maximum 2000 Lanczos iterations). The perturbation εI removes exact singularity at σ0 = 0, improving numerical stability. Denote the resulting eigenpairs as (λ2 , v2 ), . . . , (λd+1 , vd+1 ). Small eigenvalues λi ≈ 0 indicate entities co-occurring in the same dense community. We assemble the spectral coordinate matrix   U = v2 v3 · · · vd+1 ∈ Rn×d (4) p and rescale U to target standard deviation τ = 2 / (n + d): τ U (5) U ← std(U ) + ε The entity embedding table is initialized as E (0) = U . Relation embeddings retain Xavier uniform initialization because relations do not appear in the Laplacian. Interpretation. Spectral initialization places entities in the embedding space induced by normalized spectral clustering (Ng, Jordan, and Weiss 2001): entities within the same high-confidence community receive similar coordinates, while high-degree hubs bridging multiple communities occupy structurally central positions. Complexity. Building A takes O(|E|) time. The shiftinvert ARPACK call computes the d smallest eigenvectors in O(d · nnz(L)) time per Lanczos step, and typically O(d · |E|) overall for sparse real-world graphs, where nnz(L) denotes the number of non-zeros. This is a one-time pre-training cost with no effect on per-epoch training or inference.

Graph-Smoothness Regularizer Formulation. The graph Dirichlet energy of the entity embedding matrixPE under the confidence-weighted graph is tr(E ⊤ LE) = (i,j) Aij ∥ei − ej ∥2 . We add a normalized version of this energy to the CDL-RL objective: m

Lsmooth =

1 X si ∥ehi − eti ∥2 m i=1

(6)

where (hi , ri , ti , si )m = i=1 is a mini-batch of m min(2048, |E|) edges sampled uniformly with replacement from E at each training step. Eq. (6) is an unbiased Monte Carlo estimate of the full Dirichlet energy (1/|E|) tr(E ⊤ LE). Mini-batch sampling keeps the per-step overhead at O(m · d), negligible relative to the CDL-RL forward pass. Augmented objective. During the pre-PCDG phase (t < 30), the total training loss becomes L(t) = LCDL-RL + λ Lsmooth ,

t < 30

(7)

with λ = 0.01. Minimizing Lsmooth encourages entities connected by high-confidence edges to maintain similar embeddings, preserving the structural signal from spectral initialization during early training.

PCDG-Aware Scheduling Empirical observation. Leaving Lsmooth active after epoch 30 destabilizes training on CN15k. In a controlled experiment, MSE increased from 0.035 to 0.198 between epochs 29 and 39 with Lsmooth active. No comparable instability appeared on NL27k. The difference correlates with graph density: CN15k contains × 2.5 more edges per entity than NL27k, giving Lsmooth a stronger gradient signal. Mechanistic explanation. PCDG constructs pseudolabels by replacing the head or tail entity in a training triple with a uniformly sampled entity. These synthetic entities are often distant from the original entity in the confidenceweighted graph. If Lsmooth remains active, it pulls distant entity embeddings together, opposing the CDL-RL gradient that assigns the synthetic entity a new confidence score. On dense graphs, the large number of high-confidence edges amplifies the Lsmooth gradient and produces persistent gradient conflict, causing the observed MSE spike. Scheduling rule. We deactivate Lsmooth when PCDG begins its first meta-update:  λ t < 30, (t) λ = (8) 0 t ≥ 30 The cutoff at epoch 30 follows the fixed PCDG activation schedule; it is not tuned on the test set. After epoch 30, spectral initialization remains the persistent QUEST component. The structural prior in E (0) continues to shape optimization without further overhead.

Experiments Datasets We evaluate QUEST on NL27k and CN15k (Chen et al. 2019). NL27k is derived from the Never-Ending Language Learning (NELL) knowledge base (Mitchell et al. 2018), which extracts relational facts from web pages and assigns confidence scores. CN15k is derived from ConceptNet (Speer, Chin, and Havasi 2017), a multilingual semantic network encoding commonsense knowledge as weighted relations. Table 3 reports dataset statistics.

Dataset

NL27k

CN15k

Metric

MSE

MAE

MSE

MAE

UKGElogi UKGErect BEUrRE PASSLEAFDistM ult PASSLEAFComplEx PASSLEAFRotatE UKGsE UPGAT ssCDL

0.029 0.033 0.089 0.023 0.024 0.019 0.122 0.029 0.009

0.060 0.071 0.222 0.051 0.052 0.063 0.271 0.101 0.042

0.246 0.202 0.117 0.216 0.231 0.094 0.103 0.149 0.034

0.409 0.364 0.283 0.379 0.400 0.248 0.256 0.308 0.116

QUESTF ull QUESTw/o spectral init QUESTw/o graph-reg

0.009±0.0001 0.010±0.0001 0.009±0.0001

0.041±0.0009 0.044±0.0005 0.041±0.0002

0.031±0.0002 0.031±0.0001 0.030±0.0001

0.118±0.0005 0.116±0.0000 0.118±0.0004

∆

---

+2.4%

+11.8%

---

Table 1: Comparison of QUEST and baselines on NL27k and CN15k for Confidence Prediction. Best results are in bold, secondbest underlined. ∆ denotes percentage change relative to ssCDL; green indicates improvement and - - - indicates changes within ±1%. Dataset

NL27k

CN15k

Metric

WMRR

Hits@1

WMRR

Hits@1

UKGElogi UKGErect BEUrRE PASSLEAFDistM ult PASSLEAFComplEx PASSLEAFRotatE UKGsE UPGAT ssCDL

0.593 0.580 0.272 0.676 0.708 0.715 0.064 0.658 0.727

0.462 0.452 0.117 0.553 0.586 0.580 0.031 0.530 0.636

0.118 0.127 0.138 0.170 0.196 0.137 0.012 0.165 0.207

0.072 0.060 0.039 0.078 0.086 0.037 0.002 0.078 0.133

QUESTF ull QUESTw/o spectral init QUESTw/o graph-reg

0.736±0.0022 0.735±0.0028 0.734±0.0028

0.643±0.0034 0.640±0.0039 0.637±0.0043

0.212±0.0024 0.212±0.0028 0.210±0.0011

0.141±0.0020 0.138±0.0034 0.140±0.0011

∆

+1.2%

+1.1%

+2.4%

+6.0%

Table 2: Comparison of QUEST and baselines on NL27k and CN15k for Link Prediction. Best results are in bold, second-best underlined. ∆ denotes percentage improvement relative to ssCDL in green.

Dataset

#Entities

#Relations

#Quadruples

NL27k CN15k

27,221 15,000

404 36

175,412 241,158

Table 3: Statistics of the UKG datasets.

Baselines

Evaluation Protocol We evaluate QUEST on two standard UKG completion tasks: confidence prediction and link prediction. The evaluation protocol follows the unKR (Wang et al. 2024) benchmark. Confidence Prediction. For confidence prediction, the model predicts a 101-bin confidence distribution p̂ over [0, 1]. The predicted confidence is the expected bin value: s̃ =

B−1 X

b B−1 p̂b

(9)

b=0

We compare QUEST with prior UKG completion methods, including UKGE (Chen et al. 2019), PASSLEAF (Chen, Yeh, and Kuo 2021), UKGsE (Yang et al. 2022), BEUrRE (Chen et al. 2021), UPGAT (Tseng et al. 2023), and ssCDL (Wu et al. 2025), on confidence prediction and link prediction tasks.

We normalize s̃ to [0.1, 1.0] using a linear transformation: s̃ − ℓσ 0.9 + 0.1 (10) uσ − ℓσ  b   b  and uσ = Eb∼p1.0 B−1 are exwhere ℓσ = Eb∼p0.1 B−1 pected bin values under Gaussians with bandwidth σ = 0.6. ŝ =

Figure 2: Training dynamics. Validation MAE, MSE, and WMRR across epochs for the three QUEST variants on NL27k (top) and CN15k (bottom). The vertical dotted line at epoch 30 marks the activation of ssCDL’s PCDG self-training stage. The ssCDL reference is shown as a dashed grey line. We report MSE and MAE between predicted and groundtruth values. Link Prediction. We perform tail-entity prediction in the filtered setting (Chen et al. 2019). For each (h, r, t, s), we score all candidate tails. We mask entities that form known true triples in the training, validation, or test set, except the ground-truth tail t, and compute the rank of t using the standard double-argsort method. We report two metrics: P 1 i si ranki P WMRR = (11) i si Hits@1 =

1 X I[ranki = 1] |Q| i

(12)

where Q denotes the set of test queries. WMRR aggregates reciprocal ranks weighted by ground-truth confidence, while Hits@1 measures the fraction of queries where the groundtruth tail ranks first. We use the default confidence filter of 0, so all test triples contribute to LP evaluation.

with the confidence-weighted Laplacian construction in Section Confidence-Weighted Graph Laplacian. CN15k contains roughly 2.5× more edges per entity than NL27k, producing a denser Laplacian whose low-frequency eigenvectors carry a stronger community signal. The same spectral initialization therefore induces a stronger structural prior. On NL27k, the prior is weaker because the graph itself is sparser, while the pre-PCDG phase where Lsmooth reinforces that prior remains fixed at 30 of 500 epochs. PASSLEAF and UPGAT are the closest conceptual baselines: PASSLEAF introduces semi-supervised triples, while UPGAT introduces graph attention, but both score triples as scalars. Neither matches ssCDL on NL27k link prediction, and only PASSLEAFRotatE approaches ssCDL on CN15k MSE (0.094 vs. 0.034). QUEST further reduces this error from 0.094 to 0.031, a 67% reduction, without modifying the scoring function. This supports the claim in Section QUEST that initialization geometry, rather than scorer expressiveness, is the main bottleneck.

Training Dynamics Main Results Tables 1 and 2 report performance on NL27k and CN15k for two tasks. QUESTFull achieves the best result on six of eight metric-dataset combinations and ties ssCDL on the remaining two (CN15k MSE and MAE), where a QUEST ablation still outperforms every non-QUEST baseline. The gains on CN15k consistently exceed those on NL27k: +11.8% MSE and +6.0% Hits@1 on CN15k, compared with +2.4% MAE and +1.1% Hits@1 on NL27k. This pattern is consistent

Figure 2 shows that on NL27k, all three variants pass through epoch 30 smoothly. On CN15k, the two ablations spike to roughly 0.27 MAE and 0.18 MSE at epoch 30 and require 30–50 epochs to recover, while QUESTFull shows no visible discontinuity. This matches the gradient-conflict mechanism in Section PCDG-Aware Scheduling: when Lsmooth remains active after epoch 30, it pulls distant pseudo-corrupted entities together exactly when PCDG pushes them apart. The conflict scales with graph density, explaining why NL27k

Figure 3: Ablation study. Per-metric test-set values for full QUEST and the two single-component ablations across both datasets. Dashed lines mark the ssCDL baseline. Numbers above bars report ∆ vs. ssCDL in percentage points (green: improvement, red: regression, grey: |∆| < 1%). tolerates the same regularizer that destabilizes CN15k. A single scheduling rule, deactivating Lsmooth at the PCDG boundary, removes the spike on the dense graph without dataset-specific tuning. Both ablations recover to within a few percent of QUESTFull , so the final test scores understate the cost of leaving Lsmooth active. The practical issue appears during checkpoint selection: the MAE-minimizing checkpoint used by the ssCDL pipeline becomes biased toward pre-spike epochs whose representations have not yet incorporated PCDG supervision. Deactivating Lsmooth at epoch 30 removes this instability and improves reproducibility more than the small final-score gap itself.

Ablation Study Figure 3 compares QUESTFull , QUESTw/o spectral , and QUESTw/o graph-reg on both datasets. Removing spectral initialization causes a 4.5% MAE regression on NL27k versus baseline, though it still achieves a +1.1% WMRR gain. This confirms that spectral initialization is the main contributor to regression quality on the sparse graph. Removing the graph regularizer still yields a +3.3% MSE improvement on NL27k, indicating that spectral initialization is sufficient for confidence prediction. QUESTw/o graph-reg achieves the best CN15k MSE, outperforming QUESTFull on that metric alone. This is not an evidence against the schedule: the same configuration produces the spike in Figure 2, so the lower MSE is reached through an unstable trajectory and remains sensitive to checkpoint selection. No ablation Pareto-dominates QUESTFull across the eight evaluation cells. The two components address different failure modes: initialization geometry and early-stage structural drift. Combining them is the only configuration that wins or ties on all cases avoiding the epoch-30 spike.

Conclusion We introduced QUEST, a parameter-free extension of ssCDL for uncertain knowledge graph completion. QUEST initializes entities from the confidence-weighted Laplacian and uses an unbiased mini-batch Dirichlet regularizer during early training. It then deactivates the regularizer when PCDG begins, avoiding the gradient conflict observed on dense graphs. Across NL27k and CN15k, QUEST improves most confidence and link prediction metrics while removing the epoch-30 instability spike. Limitations. QUEST is evaluated on two UKG benchmarks and inherits ssCDL’s 101-bin confidence head and fixed PCDG schedule. Its one-time spectral step may become expensive on very large graphs, and its undirected Laplacian ignores relation direction and type. Broader Impact. QUEST may improve systems that reason over uncertain facts, but UKGs can encode noise, bias, and coverage gaps. Predicted confidences should not be treated as ground truth in high-stakes settings without calibration checks and human oversight.

References Chen, D.; O’Bray, L.; and Borgwardt, K. M. 2022. StructureAware Transformer for Graph Representation Learning. In Chaudhuri, K.; Jegelka, S.; Song, L.; Szepesvári, C.; Niu, G.; and Sabato, S., eds., International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, Proceedings of Machine Learning Research, 3469–3489. PMLR. Chen, X.; Boratko, M.; Chen, M.; Dasgupta, S. S.; Li, X. L.; and McCallum, A. 2021. Probabilistic Box Embeddings for Uncertain Knowledge Graph Reasoning. In Toutanova, K.;

Rumshisky, A.; Zettlemoyer, L.; Hakkani-Tür, D.; Beltagy, I.; Bethard, S.; Cotterell, R.; Chakraborty, T.; and Zhou, Y., eds., Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021, Online, June 6-11, 2021, 882–893. Association for Computational Linguistics. Chen, X.; Chen, M.; Shi, W.; Sun, Y.; and Zaniolo, C. 2019. Embedding Uncertain Knowledge Graphs. In The ThirtyThird AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, 3363–3370. AAAI Press. Chen, Z.-M.; Yeh, M.-Y.; and Kuo, T.-W. 2021. PASSLEAF: A Pool-bAsed Semi-Supervised Learning Framework for Uncertain Knowledge Graph Embedding. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5): 4019– 4026. Choudhary, N.; Rao, N.; Katariya, S.; Subbian, K.; and Reddy, C. K. 2021. Probabilistic Entity Representation Model for Reasoning over Knowledge Graphs. In Ranzato, M.; Beygelzimer, A.; Dauphin, Y. N.; Liang, P.; and Vaughan, J. W., eds., Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, Virtual, 23440–23451. Dai, H.; Njenga, N.; Whitsett, B.; Ma, C.; Deng, D.; de Ángel, S.; Tassel, A. V.; Viswanath, S.; Pellico, R.; Adelstein, I.; and Krishnaswamy, S. 2025. Learning Laplacian Eigenvectors: A Pre-training Method for Graph Neural Networks. CoRR, abs/2509.02803. Ding, K.; Wang, J.; Caverlee, J.; and Liu, H. 2022. Meta Propagation Networks for Graph Few-shot Semi-supervised Learning. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, 6524–6531. AAAI Press. Do, V. H. T. T.; Eftekhar, P.; Hosseini, S. A.; Cheung, G.; and Chou, P. A. 2024. Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors. In Globerson, A.; Mackey, L.; Belgrave, D.; Fan, A.; Paquet, U.; Tomczak, J. M.; and Zhang, C., eds., Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024. Finn, C.; Abbeel, P.; and Levine, S. 2017. Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks. In Precup, D.; and Teh, Y. W., eds., Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, Proceedings of Machine Learning Research, 1126–1135. PMLR. Kendall, A.; Gal, Y.; and Cipolla, R. 2018. Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry

and Semantics. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, 7482–7491. Computer Vision Foundation / IEEE Computer Society. Kipf, T. N.; and Welling, M. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net. Li, R.; Li, C.; Shen, Y.; Zhang, Z.; and Chen, X. 2024a. Generalizing Knowledge Graph Embedding with Universal Orthogonal Parameterization. In Salakhutdinov, R.; Kolter, Z.; Heller, K. A.; Weller, A.; Oliver, N.; Scarlett, J.; and Berkenkamp, F., eds., Forty-First International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, Proceedings of Machine Learning Research, 28040–28059. PMLR / OpenReview.net. Li, Z.; Jia, M.; Wei, Z.; and Wang, J. 2024b. Beyond Smoothness: A General Optimization Framework for Graph Neural Networks with Negative Laplacian Regularization. Neural Networks, 180: 106704. Liang, K.; Liu, Y.; Li, H.; Meng, L.; Liu, S.; Wang, S.; Zhou, S.; and Liu, X. 2024. Clustering Then Propagation: Select Better Anchors for Knowledge Graph Embedding. In Globerson, A.; Mackey, L.; Belgrave, D.; Fan, A.; Paquet, U.; Tomczak, J. M.; and Zhang, C., eds., Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024. Liu, G.; Zhao, Z.; Zhou, H.; Li, C.; and Zeng, Q. 2026. Can Pseudo-Label Be More Reliable? A Simple yet Effective Topology-Aware Graph Self-Training Method. In Koenig, S.; Jenkins, C.; and Taylor, M. E., eds., Fortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-27, 2026, 23685– 23693. AAAI Press. Mitchell, T.; Cohen, W.; Hruschka, E.; Talukdar, P.; Yang, B.; Betteridge, J.; Carlson, A.; Dalvi, B.; Gardner, M.; Kisiel, B.; Krishnamurthy, J.; Lao, N.; Mazaitis, K.; Mohamed, T.; Nakashole, N.; Platanios, E.; Ritter, A.; Samadi, M.; Settles, B.; Wang, R.; Wijaya, D.; Gupta, A.; Chen, X.; Saparov, A.; Greaves, M.; and Welling, J. 2018. Never-ending learning. Commun. ACM, 61(5): 103–115. Ng, A. Y.; Jordan, M. I.; and Weiss, Y. 2001. On Spectral Clustering: Analysis and an Algorithm. In Dietterich, T. G.; Becker, S.; and Ghahramani, Z., eds., Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canada], 849–856. MIT Press. Sani, D. 2026. Exploiting Graph-Based Structural Priors for Visual Recognition. In Koenig, S.; Jenkins, C.; and Taylor, M. E., eds., Fortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications

of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-27, 2026, 41074–41075. AAAI Press. Speer, R.; Chin, J.; and Havasi, C. 2017. ConceptNet 5.5: An Open Multilingual Graph of General Knowledge. In Singh, S.; and Markovitch, S., eds., Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, 4444–4451. AAAI Press. Tabacof, P.; and Costabello, L. 2020. Probability Calibration for Knowledge Graph Embedding Models. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. Tseng, Y.-C.; Chen, Z.-M.; Yeh, M.-Y.; and Lin, S.-D. 2023. UPGAT: Uncertainty-aware Pseudo-Neighbor Augmented Knowledge Graph Attention Network. In Kashima, H.; Idé, T.; and Peng, W.-C., eds., Advances in Knowledge Discovery and Data Mining - 27th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2023, Osaka, Japan, May 25-28, 2023, Proceedings, Part II, Lecture Notes in Computer Science, 53–65. Springer. Vashishth, S.; Sanyal, S.; Nitin, V.; and Talukdar, P. P. 2020. Composition-Based Multi-Relational Graph Convolutional Networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. Wang, B.; Li, J.; Liu, Y.; Cheng, J.; Rong, Y.; Wang, W.; and Tsung, F. 2023. Deep Insights into Noisy Pseudo Labeling on Graph Data. In Oh, A.; Naumann, T.; Globerson, A.; Saenko, K.; Hardt, M.; and Levine, S., eds., Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023. Wang, F.; Liu, K.; Medya, S.; and Yu, P. S. 2025. BANGS: Game-theoretic Node Selection for Graph Self-Training. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net. Wang, H.; Zhang, F.; Zhang, M.; Leskovec, J.; Zhao, M.; Li, W.; and Wang, Z. 2019. Knowledge-Aware Graph Neural Networks with Label Smoothness Regularization for Recommender Systems. In Teredesai, A.; Kumar, V.; Li, Y.; Rosales, R.; Terzi, E.; and Karypis, G., eds., Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, 968–977. ACM. Wang, J.; Wu, T.; Chen, S.; Liu, Y.; Zhu, S.; Li, W.; Xu, J.; and Qi, G. 2024. unKR: A Python Library for Uncertain Knowledge Graph Reasoning by Representation Learning. In SIGIR, 2822–2826. ACM. Wang, K.; Liu, Y.; and Sheng, Q. Z. 2021. Neighborhood Intervention Consistency: Measuring Confidence for Knowledge Graph Link Prediction. In Zhou, Z.-H., ed., Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, 2090–2096. ijcai.org.

Wu, T.; Zhu, S.; Wang, J.; Xu, N.; Qi, G.; and Wang, H. 2025. Uncertain Knowledge Graph Completion via SemiSupervised Confidence Distribution Learning. In The ThirtyNinth Annual Conference on Neural Information Processing Systems. Xu, L.; Chen, L.; Wang, R.; Nie, F.; and Li, X. 2023. Joint Feature and Differentiable K-NN Graph Learning Using Dirichlet Energy. In Oh, A.; Naumann, T.; Globerson, A.; Saenko, K.; Hardt, M.; and Levine, S., eds., Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023. Yang, S.; Zhang, W.; Tang, R.; Zhang, M.; and Huang, Z. 2022. Approximate Inferring with Confidence Predicting Based on Uncertain Knowledge Graph Embedding. Information Sciences, 609: 679–690. You, Y.; Chen, T.; Wang, Z.; and Shen, Y. 2023. Graph Domain Adaptation via Theory-Grounded Spectral Regularization. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net. Zhang, W.; Li, G.; Tang, J.; Li, J.; and Tsung, F. 2024. Data Imputation from the Perspective of Graph Dirichlet Energy. In Serra, E.; and Spezzano, F., eds., Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM 2024, Boise, ID, USA, October 21-25, 2024, 3237–3247. ACM. Zhou, K.; Huang, X.; Zha, D.; Chen, R.; Li, L.; Choi, S.-H.; and Hu, X. 2021. Dirichlet Energy Constrained Learning for Deep Graph Neural Networks. In Ranzato, M.; Beygelzimer, A.; Dauphin, Y. N.; Liang, P.; and Vaughan, J. W., eds., Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, Virtual, 21834–21846.

Related documents

• Spectral Initialization and Scheduled Graph Smoothness for Uncertain Knowledge Graph Completion#924682
• Spectral Initialization and Scheduled Graph Smoothness for Uncertain Knowledge Graph Completion#920448
• RADD: Retrieval-Augmented Discrete Diffusion for Multi-Modal Knowledge Graph Completion#141536
• Recipe-Controlled Decoder Audit for Structural Knowledge-Graph Completion#271850
• Structure-Feature Aligned Graph Learning via Alternating Constrained Optimization#363267