PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Initialization and Scheduled Graph Smoothness for Uncertain Knowledge Graph Completion

Md Abrar Jahin, Taufikur Rahman Fuad, Jay Pujara, Craig A. Knoblock

arXiv:2609.02519v1cs.LGcs.AI

TL;DR

UKG completion methods often initialize embeddings without the confidence-weighted graph’s global structure, limiting their structural grounding. QUEST adds spectral initialization and scheduled graph smoothness, improving most confidence and link prediction metrics across two datasets while removing the dense-graph instability spike.

  • Problem

    Existing UKG methods randomly initialize embeddings and omit global community and hub structure from the confidence-weighted graph.

    Source: Introduction · p. 1

  • Method

    QUEST uses confidence-weighted Laplacian eigenvectors for initialization and an unbiased mini-batch Dirichlet regularizer scheduled during early training.

    Source: Introduction · p. 1, Conclusion · p. 7

  • Results

    QUEST achieves the best result on six of eight metric-dataset combinations, ties the prior best on two, and removes the epoch-30 instability spike.

    Source: Main Results · p. 6, Conclusion · p. 7

  • Takeaways & Limitations

    Spectral structural priors and scheduled graph smoothness improve accuracy and training stability in UKG completion across the evaluated benchmarks.

    Source: Conclusion · p. 7

    QUEST is evaluated on only two UKG benchmarks, and its spectral step may become expensive on very large graphs while its Laplacian ignores relation direction and type.

    Source: Conclusion · p. 7

Abstract

from arXiv · show

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 pseudo-labels. 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 confidence-distribution 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

UKG completion addresses missing confidence labels through semi-supervised learning, but existing methods discard global graph structure and can become unstable on dense graphs. QUEST adds parameter-free spectral initialization and scheduled graph smoothness to preserve topology before self-training.

  • UKGs assign continuous confidence scores to triples, and completion infers missing facts despite sparse observed confidences through semi-supervised learning.Embedding uncalibration reduces reliability in downstream reasoning tasks.Source: Introduction · p. 1
  • Existing UKG methods randomly initialize entity embeddings and process triples locally, discarding global community and hub topology.The state-of-the-art ssCDL framework models confidence distributions and generates pseudo-labels for unobserved triples.Source: Introduction · p. 1
  • Topology-agnostic pseudo-labeling creates gradient conflict between smoothness and corrupted-triple ranking objectives, causing sharp error spikes on dense graphs.Uniformly corrupted entity pairs are pulled together by smoothness but pushed apart by ranking gradients.Source: Introduction · p. 1
  • QUEST initializes embeddings with the k smallest non-trivial eigenvectors of the confidence-weighted graph Laplacian, encoding high-confidence communities and hubs without trainable parameters.This spectral prior grounds initial entity representations in global topology.Source: Introduction · pp. 1–2
  • QUEST adds an unbiased mini-batch Dirichlet energy regularizer during early confidence distribution learning, then deactivates it when pseudo-labeling begins.Scheduling yields to meta-learned supervision while preserving the spectral structural prior.Source: Introduction · pp. 1–2

Related Work

Prior UKG methods address confidence estimation and label sparsity but generally discard global confidence-weighted topology or lack graph-smoothness constraints. QUEST combines confidence-weighted spectral initialization with scheduled, unbiased Laplacian regularization to preserve structural consistency without adding trainable components.

Uncertain knowledge graph completion

  • Prior UKG models use point estimates, box-intersection confidence, semi-supervised scoring, or approximate logic, but they face scaling, label-sparsity, topology, or graph-smoothness limitations.UKGE [Chen et al. 2019], BEUrRE [Chen et al. 2021], PASSLEAF [Chen, Yeh, and Kuo 2021], UPGAT, and UKGsE exemplify these limitations.Source: Related Work · p. 2

Semi-supervised and pseudo-confidence learning

  • ssCDL models full confidence distributions and generates pseudo-confidence labels through meta-learning, but randomly initializes embeddings and discards global confidence-weighted community and hub topology.Its PCDG stage is the first UKG method described here to integrate meta-learning for pseudo-confidence generation [Wu et al. 2025].Source: Related Work · p. 2
  • Uniform entity corruption in PCDG ignores structural distance, so distant corruptions can oppose graph smoothness and introduce gradient interference as noisy pseudo-labels propagate.Structure-aware pseudo-label selection outperforms topology-agnostic or uniform strategies in the cited self-training work.Source: Related Work · p. 2

Structural priors and spectral methods for KGE

  • QUEST initializes embeddings from the k smallest non-trivial eigenvectors of the confidence-weighted Laplacian, bringing community members together and placing bridging hubs near structural centers without added parameters or pre-training.This extends spectral structural priors beyond their prior use in clustering, positional encoding, and GNN pre-training.Source: Related Work · p. 2

Graph smoothness and regularization

  • QUEST applies confidence-weighted Laplacian regularization without a GNN, estimates its Dirichlet energy with unbiased mini-batches, and deactivates it when PCDG begins to avoid dense-graph gradient conflict.Existing methods keep graph regularization active throughout training, whereas QUEST schedules it around pseudo-label training.Source: Related Work · pp. 2–3

Background and Preliminaries

UKGs represent relation triples with continuous confidence scores, and this work evaluates confidence prediction and link prediction. QUEST builds on ssCDL, which jointly learns both tasks through confidence-distribution and ranking objectives.

Uncertain Knowledge Graphs

  • A UKG is a set of confidence-annotated triples (h, r, t, s), where each confidence s lies in (0, 1].Source: Uncertain Knowledge Graphs · p. 3
  • The two tasks are confidence prediction, measured by MSE and MAE, and filtered link prediction, measured by WMRR and Hits@1 (Chen et al. 2019).The setup defines n = |V|, embedding dimension d, and B = 101 confidence bins.Source: Uncertain Knowledge Graphs · p. 3
  • ssCDL (Wu et al. 2025) maps triple features to a 101-bin confidence distribution trained against a truncated Gaussian target and predicts confidence from the expected bin value.Predicted confidence is normalized to [0.1, 1.0].Source: Uncertain Knowledge Graphs · p. 3
  • ssCDL jointly combines confidence prediction and confidence-weighted margin ranking losses using Kendall uncertainty weighting (Kendall, Gal, and Cipolla 2018).The ranking loss uses negatively corrupted triples, while σ1 and σ2 are learnable task uncertainty parameters.Source: Uncertain Knowledge Graphs · p. 3

QUEST

QUEST extends ssCDL with two parameter-free structural additions: spectral entity initialization from the confidence-weighted Laplacian and an early-training graph-smoothness regularizer. The regularizer is scheduled off when PCDG begins because it can destabilize training on dense graphs, while spectral initialization remains active.

QUEST

  • QUEST adds spectral initialization and scheduled graph smoothness to ssCDL without introducing trainable parameters.Entity embeddings use Laplacian eigenvectors, while the smoothness regularizer is disabled at epoch 30 when PCDG begins.Source: QUEST · p. 3

Confidence-Weighted Graph Laplacian

  • The confidence-weighted undirected graph yields a symmetric positive-semidefinite Laplacian whose smallest non-trivial eigenvectors represent smooth community-scale structure.The constant zero-eigenvalue vector is discarded; larger eigenvalues represent increasingly local, high-frequency variation.Source: Confidence-Weighted Graph Laplacian · pp. 3–4

Spectral Entity Initialization

  • Spectral initialization sets entity embeddings to the d smallest non-trivial Laplacian eigenvectors, placing same-community entities similarly and hubs centrally.Relations retain Xavier uniform initialization because they are absent from the Laplacian; the spectral computation is a one-time pre-training cost.Source: Spectral Entity Initialization · p. 4

Graph-Smoothness Regularizer

  • The graph-smoothness regularizer minimizes confidence-weighted Dirichlet energy so high-confidence neighbors remain close during early training.Uniformly sampled mini-batches provide an unbiased estimate with m = min(2048, |E|) and O(m · d) per-step overhead; λ = 0.01 before epoch 30.Source: Graph-Smoothness Regularizer · p. 4

PCDG-Aware Scheduling

  • On CN15k, keeping smoothness active raised MSE from 0.035 to 0.198 between epochs 29 and 39, whereas NL27k showed no comparable instability.CN15k has 2.5 times more edges per entity, amplifying smoothness gradients that conflict with PCDG’s synthetic-entity updates; QUEST therefore deactivates the regularizer at epoch 30 while retaining spectral initialization.Source: PCDG-Aware Scheduling · p. 4

Experiments

QUEST achieves the strongest overall UKG completion results while combining spectral initialization with scheduled graph smoothness to improve accuracy and training stability. Experiments on NL27k and CN15k show that the full method wins or ties across all reported cases without the dense-graph instability of unscheduled regularization.

Datasets

  • Experiments use NL27k from NELL and CN15k from ConceptNet, evaluating confidence prediction and filtered tail-entity link prediction under the unKR benchmark protocol.Confidence prediction uses 101-bin distributions, while link prediction reports confidence-weighted WMRR and Hits@1 with confidence filter 0.Source: Datasets · p. 4, Evaluation Protocol · pp. 5–6

Main Results

  • QUESTFull achieves the best result on six of eight metric-dataset combinations and ties ssCDL on the remaining two, where a QUEST ablation beats every non-QUEST baseline.Tables 1 and 2 cover confidence prediction and link prediction on NL27k and CN15k.Source: Table 1 · p. 5, Table 2 · p. 5, Main Results · p. 6

Training Dynamics

  • On CN15k, the two unscheduled ablations spike to roughly 0.27 MAE and 0.18 MSE at epoch 30, whereas QUESTFull shows no visible discontinuity.Deactivating Lsmooth at the PCDG boundary removes this dense-graph instability without dataset-specific tuning and improves checkpoint reproducibility.Source: Figure 2 · p. 6, Training Dynamics · pp. 6–7

Main Results

  • On CN15k, QUEST improves MSE by 11.8% and Hits@1 by 6.0%, compared with 2.4% MAE and 1.1% Hits@1 on NL27k.CN15k has roughly 2.5× more edges per entity, strengthening the low-frequency Laplacian eigenvector community signal.Source: Main Results · p. 6

Baselines

  • On CN15k MSE, QUEST reduces PASSLEAFRotatE’s 0.094 error to 0.031, a 67% reduction, without modifying the scoring function.PASSLEAF and UPGAT are conceptually close baselines, but neither matches ssCDL on NL27k link prediction.Source: Main Results · p. 6

Ablation Study

  • Removing spectral initialization causes a 4.5% NL27k MAE regression, while removing graph regularization still improves MSE by 3.3%; no ablation Pareto-dominates QUESTFull.The graph-regularizer ablation achieves the best CN15k MSE but follows the unstable trajectory, making checkpoint selection sensitive.Source: Figure 3 · p. 7, Ablation Study · p. 7

Conclusion

QUEST is a parameter-free ssCDL extension that combines spectral initialization with scheduled Dirichlet regularization, improving most metrics across two UKG benchmarks while removing the epoch-30 instability spike. Its evaluation and design remain limited by benchmark scope, computational and structural assumptions, and the need for calibration and oversight in high-stakes use.

Conclusion

  • QUEST improves most confidence and link prediction metrics across NL27k and CN15k while removing the epoch-30 instability spike.It initializes entities from the confidence-weighted Laplacian, applies an unbiased mini-batch Dirichlet regularizer early, and deactivates it when PCDG begins to avoid dense-graph gradient conflict.Source: Conclusion · p. 7

Limitations

  • QUEST is evaluated on only two UKG benchmarks, inherits ssCDL’s 101-bin confidence head and fixed PCDG schedule, and may face expensive spectral initialization on very large graphs.Its undirected Laplacian also ignores relation direction and type.Source: Conclusion · p. 7

Broader Impact

  • Predicted confidences should not be treated as ground truth in high-stakes settings without calibration checks and human oversight.UKGs can encode noise, bias, and coverage gaps, although QUEST may improve systems that reason over uncertain facts.Source: Conclusion · p. 7

Related papers

Loading 2609.02519v1…