Understanding Expressivity of GNN in Rule Learning

• URL: http://arxiv.org/abs/2303.12306v2
• Date: Wed, 10 Apr 2024 02:32:52 GMT
• Title: Understanding Expressivity of GNN in Rule Learning
• Authors: Haiquan Qiu, Yongqi Zhang, Yong Li, Quanming Yao,
• Abstract summary: Rule learning is critical to improving knowledge graph (KG) reasoning. GNNs with tail entity scoring are unified into a common framework. We propose a novel labeling strategy to learn more rules in KG reasoning.
• Score: 36.04983130825589
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Rule learning is critical to improving knowledge graph (KG) reasoning due to their ability to provide logical and interpretable explanations. Recently, Graph Neural Networks (GNNs) with tail entity scoring achieve the state-of-the-art performance on KG reasoning. However, the theoretical understandings for these GNNs are either lacking or focusing on single-relational graphs, leaving what the kind of rules these GNNs can learn an open problem. We propose to fill the above gap in this paper. Specifically, GNNs with tail entity scoring are unified into a common framework. Then, we analyze their expressivity by formally describing the rule structures they can learn and theoretically demonstrating their superiority. These results further inspire us to propose a novel labeling strategy to learn more rules in KG reasoning. Experimental results are consistent with our theoretical findings and verify the effectiveness of our proposed method. The code is publicly available at https://github.com/LARS-research/Rule-learning-expressivity.

Related papers

• Systematic Reasoning About Relational Domains With Graph Neural Networks [17.49288661342947]
  We focus on reasoning in relational domains, where the use of Graph Neural Networks (GNNs) seems like a natural choice. Previous work on reasoning with GNNs has shown that such models tend to fail when presented with test examples that require longer inference chains than those seen during training. This suggests that GNNs lack the ability to generalize from training examples in a systematic way.
  arXiv  Detail & Related papers  (2024-07-24T16:17:15Z)
• On GNN explanability with activation rules [4.448117354676033]
  We propose to mine activation rules in the hidden layers to understand how the GNNs perceive the world. We define an effective and principled algorithm to enumerate activations rules in each hidden layer. We show that the activation rules provide insights on the characteristics used by the GNN to classify the graphs.
  arXiv  Detail & Related papers  (2024-06-17T14:42:59Z)
• ChatRule: Mining Logical Rules with Large Language Models for Knowledge Graph Reasoning [107.61997887260056]
  We propose a novel framework, ChatRule, unleashing the power of large language models for mining logical rules over knowledge graphs. Specifically, the framework is initiated with an LLM-based rule generator, leveraging both the semantic and structural information of KGs. To refine the generated rules, a rule ranking module estimates the rule quality by incorporating facts from existing KGs.
  arXiv  Detail & Related papers  (2023-09-04T11:38:02Z)
• Rethinking the Expressive Power of GNNs via Graph Biconnectivity [45.4674360883544]
  We introduce a novel class of expressivity metrics via graph biconnectivity and highlight their importance in both theory and practice. We introduce a principled and more efficient approach, called the Generalized Distance Weisfeiler-Lehman (GD-WL) Practically, we show GD-WL can be implemented by a Transformer-like architecture that preserves and enjoys full parallelizability.
  arXiv  Detail & Related papers  (2023-01-23T15:58:59Z)
• RELIANT: Fair Knowledge Distillation for Graph Neural Networks [39.22568244059485]
  Graph Neural Networks (GNNs) have shown satisfying performance on various graph learning tasks. Knowledge Distillation (KD) is a common solution to compress GNNs. We propose a principled framework named RELIANT to mitigate the bias exhibited by the student model.
  arXiv  Detail & Related papers  (2023-01-03T15:21:24Z)
• RulE: Knowledge Graph Reasoning with Rule Embedding [69.31451649090661]
  We propose a principled framework called textbfRulE (stands for Rule Embedding) to leverage logical rules to enhance KG reasoning. RulE learns rule embeddings from existing triplets and first-order rules by jointly representing textbfentities, textbfrelations and textbflogical rules in a unified embedding space. Results on multiple benchmarks reveal that our model outperforms the majority of existing embedding-based and rule-based approaches.
  arXiv  Detail & Related papers  (2022-10-24T06:47:13Z)
• Jointly Attacking Graph Neural Network and its Explanations [50.231829335996814]
  Graph Neural Networks (GNNs) have boosted the performance for many graph-related tasks. Recent studies have shown that GNNs are highly vulnerable to adversarial attacks, where adversaries can mislead the GNNs' prediction by modifying graphs. We propose a novel attack framework (GEAttack) which can attack both a GNN model and its explanations by simultaneously exploiting their vulnerabilities.
  arXiv  Detail & Related papers  (2021-08-07T07:44:33Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  Graph Neural Networks (GNNs) have been studied from the lens of expressive power and generalization. We study the dynamics of GNNs by studying deep skip optimization. Our results provide first theoretical support for the success of GNNs.
  arXiv  Detail & Related papers  (2021-05-10T17:59:01Z)
• Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels [25.736529232578178]
  Graph neural networks (GNNs) have achieved tremendous success in graph mining. MPGNNs, as the prevailing type of GNNs, have been theoretically shown unable to distinguish, detect or count many graph substructures. We propose GSKN, a GNN model with a theoretically stronger ability to distinguish graph structures.
  arXiv  Detail & Related papers  (2021-04-07T08:50:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.