Position Spaces and Graphs
In this paper, we introduce position graphs, a graph-based reasoning framework based on the formalization of position spaces. This framework utilizes two strict partial orders, representing horizontal and vertical alignment and precedence, to model the relative positions of discrete tokens. Unlike general qualitative spatial calculi, position graphs are constrained by a chain condition and compatibility requirements that focus on rows and columns. We provide a comprehensive theoretical analysis of this representation, beginning with a characterization of graph consistency. Conditions to ensure the consistency of position graphs are established. Furthermore, we investigate the computational complexity of structural pattern discovery, modeled as the induced subgraph isomorphism problem. We demonstrate that this problem remains NP-complete even within the restricted class of position graphs. While initially motivated by document processing, this work focuses on the underlying mathematical properties and algebraic consistency of position-based constraints, providing a formal logical layer that is independent of specific data extraction techniques.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Orthogonal Transforms for Signals on Directed Graphs
In this paper we consider the problem of defining transforms for signals on directed graphs, with a specific focus on defective graphs where the corresponding graph operator cannot be diagonalized. Our proposed method is…
Tiered Latent Representations and Latent Spaces for Molecular Graphs
Molecular graphs generally contain subgraphs (known as groups) that are identifiable and significant in composition, functionality, geometry, etc. Flat latent representations (node embeddings or graph embeddings) fail to…
On the Stability of Expressive Positional Encodings for Graphs
Designing effective positional encodings for graphs is key to building powerful graph transformers and enhancing message-passing graph neural networks. Although widespread, using Laplacian eigenvectors as positional enco…
Molecular Property PredictionOut-of-Distribution GeneralizationProperty PredictionTraversing Knowledge Graphs in Vector Space
Path queries on a knowledge graph can be used to answer compositional questions such as "What languages are spoken by people living in Lisbon?". However, knowledge graphs often have missing facts (edges) which disrupts p…
Knowledge Base CompletionKnowledge GraphsAttending to Topological Spaces: The Cellular Transformer
Topological Deep Learning seeks to enhance the predictive performance of neural network models by harnessing topological structures in input data. Topological neural networks operate on spaces such as cell complexes and …