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 must infer confidence for largely unobserved triples, while existing initialization overlooks the confidence-weighted graph’s global structure and pseudo-labeling can conflict with graph smoothness. QUEST adds parameter-free spectral initialization and scheduled, unbiased mini-batch Dirichlet regularization to the standard pipeline. Across two UKG datasets, it improves six of eight metric-dataset pairs, matches the prior best on two, and removes the dense-graph instability spike.

  • Problem

    Existing UKG methods randomly initialize entity embeddings and overlook global community and hub topology, while pseudo-labeling can conflict with graph smoothness.

  • Method

    QUEST initializes embeddings with confidence-weighted Laplacian eigenvectors and applies an unbiased mini-batch Dirichlet regularizer that is deactivated when pseudo-labeling begins.

  • Results

    QUEST achieves the best result on six of eight metric-dataset combinations, ties ssCDL on the remaining two, and removes the dense-graph instability spike.

  • Takeaways & Limitations

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

  • Takeaways & Limitations

    QUEST is evaluated on two UKG benchmarks, inherits ssCDL’s 101-bin confidence head and fixed PCDG schedule, and uses an undirected Laplacian that ignores relation direction and type.

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.

Spectral Initialization and Scheduled Graph Smoothness

The paper is authored by Md Abrar Jahin, Taufikur Rahman Fuad, Jay Pujara, and Craig A. Knoblock.

  • Md Abrar Jahin is listed as an author.
  • Taufikur Rahman Fuad is listed as an author.
  • Jay Pujara and Craig A. Knoblock are listed as authors.

Introduction

UKG completion must infer confidence for missing triples, but existing methods overlook global graph structure and can create optimization conflicts during pseudo-labeling. QUEST addresses this gap with spectral initialization, scheduled graph smoothness, and no additional trainable parameters.

  • Introduction: UKGs assign continuous confidence scores to triples, while most possible triples lack observed confidences.This makes UKG completion inherently dependent on semi-supervised learning.
  • Introduction: Existing methods randomly initialize entity embeddings and process triples locally, discarding global community and hub topology.
  • Introduction: Topology-agnostic pseudo-labeling can propagate errors, while smoothness and ranking gradients conflict when corrupted entities are structurally distant.
  • Introduction: QUEST initializes embeddings with the k smallest non-trivial eigenvectors of the confidence-weighted graph Laplacian.The initialization places entities from high-confidence communities near one another and centers high-degree hubs.
  • Introduction: QUEST adds an unbiased mini-batch Dirichlet-energy regularizer that enforces early-stage topological smoothness without additional trainable parameters.The regularizer is deactivated when pseudo-labeling begins, preserving the spectral prior while yielding to meta-learned supervision.

Related Work

Prior UKG methods model confidence through deterministic scores, geometric representations, or semi-supervised pseudo-labeling, while spectral and smoothness techniques provide structural alternatives. QUEST combines these ideas without added trainable components and schedules smoothness around pseudo-confidence training.

  • Uncertain knowledge graph completion: UKGE maps bilinear scores to confidence values, whereas BEUrRE estimates confidence through box-intersection volumes.
  • Semi-supervised and pseudo-confidence learning for UKGs: ssCDL uses meta-learning to generate soft pseudo-confidence targets for uniformly corrupted entity pairs.
  • Semi-supervised and pseudo-confidence learning for UKGs: Uniform entity corruption can oppose graph smoothness when corrupted entities lie far from their originals, introducing gradient interference.
  • Structural priors and spectral methods for KGE: Spectral methods encode community and hub structure as a parameter-free alternative to trainable structure-aware components.
  • Structural priors and spectral methods for KGE: QUEST initializes embeddings from confidence-weighted Laplacian eigenvectors, placing community members near one another and bridging hubs near structural centers.
  • Graph smoothness and regularization: QUEST estimates graph smoothness through unbiased mini-batch sampling and deactivates the regularizer when PCDG begins.
  • Graph smoothness and regularization: The scheduled design avoids gradient conflict between pseudo-label training and graph smoothness on dense graphs.

Background and Preliminaries

A UKG represents confidence-annotated relational triples, and the paper evaluates confidence and link prediction with distinct metrics. QUEST builds on ssCDL’s confidence-distribution and ranking pipeline.

  • Uncertain Knowledge Graphs: A UKG is a tuple of entities, relation types, and confidence-annotated triples.Each triple records a head, relation, tail, and confidence s in (0, 1].
  • Uncertain Knowledge Graphs: Confidence prediction estimates triple confidence using MSE and MAE, while link prediction ranks candidate tails using WMRR and Hits@1.Link prediction uses the filtered setting.
  • ssCDL backbone: ssCDL learns entity and relation embeddings and jointly supports confidence prediction and link prediction over uncertain triples.
  • ssCDL backbone: A confidence distribution learner maps triple features to 101 confidence bins and predicts confidence from the expected bin value.The output is normalized to [0.1, 1.0].
  • ssCDL backbone: A second scoring network performs link prediction with a confidence-weighted margin-ranking loss over negatively corrupted triples.
  • ssCDL backbone: Confidence and ranking losses are combined using Kendall uncertainty weighting with learnable task-uncertainty parameters.

QUEST

QUEST extends ssCDL with two parameter-free additions: spectral entity initialization from a confidence-weighted graph Laplacian and an early-training graph-smoothness regularizer.

  • QUEST initializes entity embeddings from the k smallest non-trivial eigenvectors of the confidence-weighted Laplacian L = D − A.This encodes community structure and hub topology before training begins.
  • QUEST adds Lsmooth to the CDL-RL objective to penalize high-confidence neighbors whose entity embeddings drift apart during early training.A stability analysis motivates disabling this regularizer when PCDG begins at epoch 30.
  • The confidence-weighted graph aggregates triple confidences over entity pairs and treats directed knowledge-graph edges as undirected, producing a symmetric adjacency matrix.The degree matrix is D = diag(A1), and the Laplacian is L = D − A.

L = D −A (2)

QUEST uses Laplacian spectral coordinates to initialize entity embeddings and applies an unbiased mini-batch Dirichlet-energy regularizer only before PCDG activation. The schedule preserves the structural prior while avoiding dense-graph instability.

  • Spectral basis: The smallest non-trivial Laplacian eigenvectors encode smooth community-scale signals, while larger eigenvectors represent local high-frequency variations.The constant eigenvector for λ1 = 0 is discarded, and the remaining eigenvectors form the spectral basis.
  • Spectral initialization: QUEST computes d smallest non-trivial eigenvectors of the Tikhonov-regularized Laplacian and initializes the entity embedding table with the resulting spectral coordinates.The perturbation εI removes exact singularity at σ0 = 0; relation embeddings retain Xavier uniform initialization.
  • Spectral initialization: Spectral initialization gives same-community entities similar coordinates and places high-degree hubs in structurally central positions.Building the graph takes O(|E|), while the eigenvector computation is a one-time pre-training cost with no per-epoch or inference overhead.
  • Graph smoothness: The Dirichlet energy tr(E⊤LE) equals a confidence-weighted sum of squared embedding differences, and QUEST adds its normalized form to the CDL-RL objective.This encourages connected entities to maintain similar embeddings during early training.
  • Graph smoothness: An unbiased mini-batch estimate samples m = min(2048, |E|) edges uniformly with replacement, keeping per-step overhead at O(m · d).The estimate is unbiased for the full normalized Dirichlet energy.
  • Scheduled regularization: MSE increased from 0.035 to 0.198 between epochs 29 and 39 on CN15k when Lsmooth remained active, whereas no comparable instability appeared on NL27k.The difference correlates with CN15k having 2.5 times more edges per entity than NL27k.
  • Scheduled regularization: Uniform entity corruption can select graph-distant synthetic entities, creating gradient conflict between graph smoothness and pseudo-label confidence learning.Dense graphs amplify the smoothness gradient, motivating the schedule.
  • Scheduled regularization: QUEST deactivates Lsmooth when PCDG begins its first meta-update, following the fixed epoch-30 schedule rather than test-set tuning.After epoch 30, spectral initialization remains the persistent structural prior without further regularization overhead.

Experiments

QUEST is evaluated on NL27k and CN15k for confidence prediction and filtered link prediction, with full QUEST outperforming or matching ssCDL across all eight metric-dataset combinations. Ablations and training dynamics show that spectral initialization and scheduled graph regularization improve structural performance and avoid dense-graph instability.

  • Main results: QUESTFull achieves the best result on six of eight metric-dataset combinations and ties ssCDL on the remaining two.The ties are CN15k MSE and MAE, where a QUEST ablation still outperforms every non-QUEST baseline.
  • Main results: +11.8% MSE and +6.0% Hits@1 gains occur on CN15k, compared with +2.4% MAE and +1.1% Hits@1 gains on NL27k.The larger CN15k gains are consistent with its denser confidence-weighted graph and stronger low-frequency spectral community signal.
  • Baseline comparison: QUEST reduces PASSLEAFRotatE’s CN15k MSE from 0.094 to 0.031, a 67% reduction, without modifying the scoring function.PASSLEAF and UPGAT are the closest conceptual baselines, but neither matches ssCDL on NL27k link prediction.
  • Training dynamics: At epoch 30 on CN15k, the two ablations spike to roughly 0.27 MAE and 0.18 MSE, whereas QUESTFull shows no visible discontinuity.The spike occurs when graph smoothness remains active after PCDG begins; deactivating it at the boundary removes the instability without dataset-specific tuning.
  • Training dynamics: Deactivating Lsmooth at epoch 30 improves checkpoint reliability because otherwise MAE-based selection favors pre-spike representations that have not incorporated PCDG supervision.Both ablations recover to within a few percent of QUESTFull, so final test scores understate the cost of the unstable trajectory.
  • Ablation study: Removing spectral initialization causes a 4.5% MAE regression on NL27k, while removing graph regularization still yields a +3.3% MSE improvement.The ablation results indicate that spectral initialization is the main contributor to regression quality on the sparse graph, while the regularizer addresses early-stage structural drift.

Conclusion

QUEST combines confidence-weighted spectral initialization with an early-training Dirichlet regularizer in a parameter-free extension of ssCDL. Across two UKG datasets, it improves most confidence and link-prediction metrics while removing the epoch-30 instability spike, but its evaluation and structural assumptions remain bounded.

  • Conclusion: QUEST is a parameter-free extension of ssCDL that initializes entities from the confidence-weighted Laplacian and regularizes early training with unbiased mini-batch Dirichlet energy.The regularizer is deactivated when PCDG begins to avoid the gradient conflict observed on dense graphs.
  • Conclusion: 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.
  • Limitations: The one-time spectral step may become expensive on very large graphs, while the undirected Laplacian ignores relation direction and type.
  • Broader Impact: Predicted confidences should not be treated as ground truth in high-stakes settings without calibration checks and human oversight.
Loading 2609.02519v1…