PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimating Node Importance in Knowledge Graphs Using Graph Neural Networks

Namyong Park, Andrey Kan, Xin Luna Dong, Tong Zhao, Christos Faloutsos

arXiv:1905.08865v2cs.LGcs.IRstat.ML

TL;DR

Node importance estimation in knowledge graphs must use sparse known scores and heterogeneous relations while generalizing across entities and node types. The paper introduces GENI, a GNN that aggregates scores with predicate-aware attention and applies flexible centrality adjustment. On real-world KGs, GENI achieves 5–17% higher NDCG@100 than the state of the art.

  • Problem

    Estimating node importance from known scores and KG auxiliary information is difficult because existing methods do not fully use predicates or flexibly model complex entity–importance relationships.

  • Method

    GENI is a GNN that aggregates intermediate importance scores through predicate-aware attention and adjusts them using node centrality.

  • Results

    5–17% higher NDCG@100 than the state of the art: GENI outperforms existing approaches on real-world KGs.

  • Takeaways & Limitations

    GENI provides a flexible KG-specific approach for estimating node importance, supporting applications such as item recommendation and resource allocation.

  • Takeaways & Limitations

    Available importance scores are often limited in number and type, making generalization across in-domain and out-of-domain estimation challenging.

Abstract

from arXiv · show

How can we estimate the importance of nodes in a knowledge graph (KG)? A KG is a multi-relational graph that has proven valuable for many tasks including question answering and semantic search. In this paper, we present GENI, a method for tackling the problem of estimating node importance in KGs, which enables several downstream applications such as item recommendation and resource allocation. While a number of approaches have been developed to address this problem for general graphs, they do not fully utilize information available in KGs, or lack flexibility needed to model complex relationship between entities and their importance. To address these limitations, we explore supervised machine learning algorithms. In particular, building upon recent advancement of graph neural networks (GNNs), we develop GENI, a GNN-based method designed to deal with distinctive challenges involved with predicting node importance in KGs. Our method performs an aggregation of importance scores instead of aggregating node embeddings via predicate-aware attention mechanism and flexible centrality adjustment. In our evaluation of GENI and existing methods on predicting node importance in real-world KGs with different characteristics, GENI achieves 5-17% higher NDCG@100 than the state of the art.

1 INTRODUCTION

Knowledge graphs support many applications, but estimating node importance remains challenging because existing methods do not fully use multi-relational information or learn flexibly from ground truth. GENI addresses these gaps with predicate-aware score aggregation and centrality adjustment, outperforming prior methods on real-world KGs.

  • Motivation: Knowledge graphs encode heterogeneous information through multiple relation types and support applications including question answering, recommendation, semantic search, and knowledge completion.Nodes represent entities, while edges represent typed subject–predicate–object facts.
  • Motivation: Node importance estimation supports recommendation, query disambiguation, and resource allocation optimization.Importance can help select among ambiguous entities and prioritize limited validation resources.
  • Research gap: Existing methods such as PageRank, Personalized PageRank, and HAR do not jointly provide learnable, predicate-aware modeling grounded in known importance scores.Their fixed propagation structures rely on prior assumptions and contain no parameters optimized against ground truth.
  • Approach: GENI is a GNN that uses predicate-aware attention to aggregate importance scores and flexibly adjusts scores according to node centrality.It is designed to model relationships between neighboring-node importance while incorporating KG-specific information.
  • Results: 5%-17% percentage points: GENI outperforms the state of the art on real-world KGs, according to Figure 2.The reported comparison concerns node-importance prediction in real KGs.

2 PRELIMINARIES

The paper formalizes KGs as multi-relational graphs and node importance estimation as learning scores for every node from scores known for a subset. It identifies generalization across node types and several modeling desiderata for supervised estimation.

  • Problem definition: A KG is a multi-relational graph whose nodes are entities and whose typed edges represent relationships between them.The number of predicate types is P, with edge set E_p for predicate p.
  • Problem definition: An importance score is a non-negative real value representing a node’s significance or popularity, with one shared score set enabling comparisons.Examples include movie gross and entity pageviews.
  • Problem definition: Node importance estimation learns S: V → [0, ∞) from scores for a subset of nodes to estimate every node’s importance.The supervised framework seeks estimates that reflect true importance as closely as possible.
  • Problem definition: In-domain estimation predicts nodes of a scored type, whereas out-of-domain estimation predicts nodes of other types.The distinction is defined relative to the type T containing the initially scored nodes.
  • Challenge: Limited numbers and types of known importance scores make generalization across both estimation settings a central challenge.The method is expected to address cases where scores are available for only some node types.
  • Design desiderata: The method desiderata include neighborhood awareness, predicate use, centrality awareness, input-score use, and flexible adaptation.These criteria guide comparison between GENI and existing methods.
  • Graph neural networks: GNNs update node representations by repeatedly aggregating neighborhood features across layers, allowing information from progressively higher-order neighbors to be captured.Aggregation, transformation, and combination functions define the generic architecture.

3 METHOD

GENI estimates KG node importance by directly aggregating neighboring scores with predicate-aware attention, then adjusting the result using flexible centrality information. Its architecture supports multiple score-aggregation layers and heads to incorporate broader neighborhoods.

  • 3.1 Score Aggregation: GENI directly aggregates neighboring importance scores instead of node embeddings to model relationships between node importance values.The aggregation uses the node and its neighbors’ intermediate score estimations.
  • 3.1 Score Aggregation: GENI computes initial node-importance estimates from input feature vectors using a scoring network.The scoring network may use one-hot, manually extracted, or learned node features.
  • 3.2 Predicate-Aware Attention Mechanism: Predicate-aware attention weights neighboring scores using both relation types and intermediate node scores.Shared predicate embeddings represent relation types, while attention is computed through a shared self-attention mechanism and normalized with softmax.
  • 3.3 Centrality Adjustment: GENI adjusts final score estimates with learnable centrality scaling and shifting to accommodate cases where in-degree poorly represents centrality.The initial centrality proxy is log(d(i) + ϵ), based on node in-degree.
  • 3.4 Model Architecture: Multiple score-aggregation layers expand the neighborhood used for estimation, while variable numbers of heads provide flexible aggregation capacity.Each head independently produces a score estimation, and outputs are averaged before the next layer.

4 EXPERIMENTS

The experiments evaluate node-importance methods on real-world knowledge graphs using in-domain and out-of-domain ranking and correlation metrics. GENI consistently performs strongly, while predicate modeling, centrality adjustment, and architecture choices affect performance.

  • Datasets: Four real-world knowledge graphs with different characteristics are evaluated using in-domain and out-of-domain prediction settings.The datasets include fb15k, music10k, tmdb5k, and imdb.
  • Methods: The study compares non-trainable methods including PageRank, Personalized PageRank, and HAR with supervised regression, random forests, neural networks, GAT, and GENI.All methods use the same node features and input importance scores.
  • In-domain results: GENI outperforms all baselines on all four datasets for both in-domain NDCG@100 and Spearman correlation.Supervised approaches generally outperform non-trainable methods in-domain, while GENI improves further over GAT by modeling neighboring score relationships.
  • Out-of-domain results: GENI achieves the best out-of-domain results for every KG on both NDCG@100 and NDCG@2000.Non-trainable methods can outperform supervised baselines when known scores are scarce, whereas supervised methods perform better on imdb with more labeled nodes.
  • Predicate modeling: 3.6% higher NDCG@100 and 12.7% higher Spearman result when each predicate receives a dedicated embedding.The gains indicate that predicate-specific representations improve modeling of relations between node-importance scores.
  • Centrality adjustment: 8% higher NDCG@100 and 27% higher Spearman result from flexible rather than fixed centrality adjustment on fb15k.The comparison is reported where node centrality is poorly aligned with input scores.
  • Parameter sensitivity: Spearman increases from 0.72 to 0.77 when the number of score-aggregation heads rises from 1 to 5.Performance generally improves with more aggregation layers and heads, while excessive predicate-embedding dimensions can hurt performance.

5 RELATED WORK

Related work includes graph-based importance methods and graph neural networks. Existing importance methods differ in how they use graph structure, edge types, and known importance scores.

  • Node importance estimation: PageRank estimates node importance from the limiting probability of a random surfer moving through the graph.Its scores are determined by graph structure and do not use known importance scores.
  • Node importance estimation: Personalized PageRank incorporates user-provided notions of node importance, while HAR distinguishes predicates in knowledge graphs.The figure passage notes that conventional methods are not well suited to KGs when they ignore edge types.
  • Graph neural networks: Graph neural networks learn from arbitrarily structured graph data and include formulations based on graph convolutions.Early spectral formulations required graph-Laplacian eigendecomposition and were computationally costly.

6 CONCLUSION

The paper concludes that GENI estimates node importance by combining predicate-aware score aggregation with flexible centrality adjustment. On real-world knowledge graphs, it outperforms existing approaches and achieves 5–17% higher NDCG@100 than the state of the art.

  • Conclusion: GENI uses predicate-aware attention for score aggregation and flexible centrality adjustment to model relationships between entities and their importance.The method is designed to use rich knowledge-graph information flexibly.
  • Conclusion: 5–17% higher NDCG@100 than the state of the art is achieved by GENI on real-world knowledge graphs.The evaluation covers knowledge graphs with different characteristics.
  • Conclusion: Future work will consider multiple independent input sources for node importance.

A DATASETS

The dataset suite contains four knowledge graphs constructed from public sources, with importance scores derived from pageviews, popularity, votes, or external rankings. Score preprocessing differs between datasets according to their distributions.

  • fb15k: fb15k is built from Freebase and uses Wikipedia pageviews as entity importance scores.The dataset has many predicates and higher density than the other evaluated knowledge graphs, and does not receive OOD evaluation.
  • music10k: music10k is constructed from Million Song Dataset data with song, artist, and album entities connected by corresponding edge types.Song hotttnesss is used as input importance, while artist hotttnesss is used for OOD evaluation.
  • tmdb5k: tmdb5k is constructed from movie, genre, company, country, crew, and cast entities linked by typed relations.Movie popularity is used as importance, while worldwide box-office grosses rank directors for OOD evaluation.
  • imdb: imdb is constructed from public IMDb tables and focuses on movie-related titles, genres, directors, writers, casts, and crews.Movie vote counts provide importance scores, and the same director ranking as tmdb5k is used for OOD evaluation.
  • Score preprocessing: Scores for fb15k, tmdb5k, and imdb are offset by 1 and log-transformed, whereas music10k scores are used without log transformation.The transformation reflects the highly skewed distributions of the first group and the 0-to-1 range of music10k scores.

B EXPERIMENTAL SETTINGS

The experiments use standard graph, machine-learning, and deep-learning libraries to implement the KG methods and baselines.

  • Other Libraries and Algorithms: The implementation used Python 3.6.
  • Graph Library: NetworkX 2.1 represented all KGs as MultiDiGraph objects because entities can share multiple edges with different types.NetworkX’s pagerank_scipy function implemented PageRank and Personalized PageRank.
  • Machine Learning Library: TensorFlow 1.12 implemented deep-learning models, while scikit-learn 0.20.0 supported random forest and linear regression.
  • Other Libraries and Algorithms: GAT used the authors’ reference TensorFlow implementation, HAR was implemented from its algorithm description, and node2vec used its project implementation.NumPy 1.15 and SciPy 1.1.0 supported data manipulation.

B.3 Hyperparameters and Configurations

The study configures conventional, neural, attention-based, and GENI models with dataset-specific architectures and training settings, while using node2vec to generate supervised-method features.

  • Baseline Configurations: HAR uses normalized input scores as entity probabilities, equal probability across relations, and a maximum of 30 iterations.Its settings are α = 0.15, β = 0.15, and γ = 0.
  • Baseline Configurations: Linear regression and random forests use scikit-learn’s default parameter values.
  • Neural Networks: The standard neural network uses architecture [NF, 0.5×NF, 0.25×NF, 1] with ReLU activations and Adam optimization.Its learning rate is α = 0.001, with β1 = 0.9, β2 = 0.999, and weight decay 0.0005.
  • Graph Attention Networks: GAT uses two attention layers with four heads each, followed by a fully connected neural network.Attention computation uses a Leaky ReLU with negative slope 0.2, while attention-head outputs use ELU.
  • GENI: GENI uses four score-aggregation heads per layer, with three layers for fb15k and one layer for other KGs.Its ScoringNetwork has architecture [NF, 0.75 × NF, 1], and predicate embeddings have dimension 10.
  • Node Features: Node2vec generates node features with 64 output dimensions for fb15k, music10k, and tmdb5k, and 128 for imdb.

C.1 Case Study

The case study compares GENI, HAR, and GAT on in-domain movie ranking and out-of-domain director ranking using estimated importance scores.

  • In-domain estimation: GENI’s in-domain top-10 movie predictions have rank differences below 100 for every prediction.For GAT and HAR, three movies have differences greater than 100 between ground-truth and predicted ranks.
  • Out-of-domain estimation: GENI and HAR produce similar out-of-domain director rankings, with five directors appearing in both lists.Steven Spielberg is one example of a director appearing in both rankings.
  • Out-of-domain estimation: GAT’s out-of-domain ranking is substantially worse, with nine of ten predictions absent from the top-200 highest-earning directors.
  • Out-of-domain estimation: GENI’s centrality-aware ranking is reported as more consistent with the director ground truth.

C.2 Regression Performance Evaluation for In-Domain Predictions

The regression evaluation measures how accurately supervised methods recover in-domain node importance scores, using RMSE on four real-world datasets.

  • Regression evaluation: GENI performs better than every other supervised method on all four real-world datasets.The evaluation reports RMSE, where lower values indicate better performance.
  • Regression evaluation: Regression performance follows a trend similar to the supervised methods’ ranking-measure performance reported in Table 4.
  • Evaluation design: Non-trainable methods are excluded because their outputs are not on the same scale as the input importance scores.
Loading 1905.08865v2…