Graph Parsing as Sequence Labeling

Abstract

[Abstract]: Graph processing is a fundamental task in Computer Science and Artificial Intelligence that involves modeling relationships between nodes in structured data. State-of-the-art approaches, while effective, suffer from quadratic complexity since they process all possible paired connections between the nodes of an input graph, making them computationally expensive for large-scale applications. To address this challenge, we incorporate the principles of the sequence-labeling paradigm to graph parsing, proposing new graph linearizations that encode graph structures as sequences of labels. This transformation enables parsing with linear complexity, significantly improving efficiency. Our work builds on state-of-the-art neural sequence-labeling frameworks and introduces both bounded and unbounded linearizations tailored for graph parsing. We conduct an empirical evaluation, comparing our approach against traditional graph-based methods on benchmark datasets. The results demonstrate that our proposed linearizations achieve competitive performance while reducing computational overhead, paving the way for more scalable and efficient graph processing.