A Prufer-Sequence Based Representation of Large Graphs for Structural Encoding of Logic Networks
Manjari Pradhan, Bhargab B. Bhattacharya · 2019
Graphs appear ubiquitously in diverse real-world applications that span a wide spectrum including communication infrastructure, biological and social networks, Internet-of-Things, and VLSI circuits. Such applications inherently involve huge volume of data, and feeding them as inputs to advanced machine-learning tools ever remains elusive. While the representation of the underlying graph has to be compact, it must also capture aptly the structural diversity of different graphs/networks so that the learning engines can be suitably trained. We observe that two factors are responsible for making this gulf wider. First, a large graph representing real data is memory-strenuous, and may have non-Euclidean attributes; secondly, most of the deep-learning tools perform better on low-dimensional, Euclidean or structured data such as text or graphic images. In this work, we propose a linear encoding of graphs based on Prufer-sequence that provides an efficient mechanism to preserve their structural information. Experimental results on directed acyclic graphs representing digital integrated-circuit netlists, establish the efficacy of such encoding.