On the Expressiveness and Learning of Relational Neural Networks on Hypergraphs
This paper presents a framework for analyzing the expressiveness and learning of relational models applied to hypergraph reasoning tasks. We start with a general framework that unifies several relational neural network architectures: graph neural networks, neural logical machines, and transformers. Our first contribution is a fine-grained analysis of the expressiveness of these neural networks, that is, the set of functions that they can realize and the set of problems that they can solve. Our result is a hierarchy of problems they can solve, defined in terms of various hyperparameters such as depth and width. Next, we analyze the learning properties of these neural networks, especially focusing on how they can be trained on a small graphs and generalize to larger graphs. Our theoretical results are further supported by the empirical results illustrating the optimization and generalization of these models based on gradient-descent training.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Link Prediction with Relational Hypergraphs
Link prediction with knowledge graphs has been thoroughly studied in graph machine learning, leading to a rich landscape of graph neural network architectures with successful applications. Nonetheless, it remains challen…
Graph Neural NetworkInductive Link PredictionKnowledge GraphsLink Prediction+1HyperRAG: Reasoning N-ary Facts over Hypergraphs for Retrieval Augmented Generation
Graph-based retrieval-augmented generation (RAG) methods, typically built on knowledge graphs (KGs) with binary relational facts, have shown promise in multi-hop open-domain QA. However, their rigid retrieval schemes and…
Knowledge GraphsKnowledge Hypergraph Embedding Meets Relational Algebra
Embedding-based methods for reasoning in knowledge hypergraphs learn a representation for each entity and relation. Current methods do not capture the procedural rules underlying the relations in the graph. We propose a …
hypergraph embeddingKnowledge GraphsLink PredictionEnhancing the Utility of Higher-Order Information in Relational Learning
Higher-order information is crucial for relational learning in many domains where relationships extend beyond pairwise interactions. Hypergraphs provide a natural framework for modeling such relationships, which has moti…
Relational ReasoningNeural Message Passing for Multi-Relational Ordered and Recursive Hypergraphs
Message passing neural network (MPNN) has recently emerged as a successful framework by achieving state-of-the-art performances on many graph-based learning tasks. MPNN has also recently been extended to multi-relational…