Let There Be Order: Rethinking Ordering in Autoregressive Graph Generation
| dc.contributor.author | Bu, Jie | en |
| dc.contributor.author | Mehrab, Kazi Sajeed | en |
| dc.contributor.author | Karpatne, Anuj | en |
| dc.date.accessioned | 2024-02-27T13:53:52Z | en |
| dc.date.available | 2024-02-27T13:53:52Z | en |
| dc.date.issued | 2023 | en |
| dc.description.abstract | Conditional graph generation tasks involve training a model to generate a graph given a set of input conditions. Many previous studies employ autoregressive models to incrementally generate graph components such as nodes and edges. However, as graphs typically lack a natural ordering among their components, converting a graph into a sequence of tokens is not straightforward. While prior works mostly rely on conventional heuristics or graph traversal methods like breadth-first search (BFS) or depth-first search (DFS) to convert graphs to sequences, the impact of ordering on graph generation has largely been unexplored. This paper contributes to this problem by: (1) highlighting the crucial role of ordering in autoregressive graph generation models, (2) proposing a novel theoretical framework that perceives ordering as a dimensionality reduction problem, thereby facilitating a deeper understanding of the relationship between orderings and generated graph accuracy, and (3) introducing "latent sort," a learning-based ordering scheme to perform dimensionality reduction of graph tokens. Our experimental results showcase the effectiveness of latent sort across a wide range of graph generation tasks, encouraging future works to further explore and develop learning-based ordering schemes for autoregressive graph generation. | en |
| dc.description.version | Submitted version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.orcid | Karpatne, Anuj [0000-0003-1647-3534] | en |
| dc.identifier.uri | https://hdl.handle.net/10919/118191 | en |
| dc.identifier.volume | abs/2305.15562 | en |
| dc.language.iso | en | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | Let There Be Order: Rethinking Ordering in Autoregressive Graph Generation | en |
| dc.title.serial | CoRR | en |
| dc.type | Article | en |
| dc.type.dcmitype | Text | en |
| pubs.organisational-group | /Virginia Tech | en |
| pubs.organisational-group | /Virginia Tech/Engineering | en |
| pubs.organisational-group | /Virginia Tech/Engineering/Computer Science | en |
| pubs.organisational-group | /Virginia Tech/All T&R Faculty | en |
| pubs.organisational-group | /Virginia Tech/Engineering/COE T&R Faculty | en |