Compression-based inference on graph data

We investigate the use of compression-based learning on graph data. General purpose compressors operate on bitstrings or other sequential representations. A single graph can be represented sequentially in many ways, which may in uence the performance of sequential compressors. Using Normalized Compression Distance (NCD), we test a sequential compressor versus a native
graph compressor. We use both synthetic, randomly generated graphs and reallife datasets. We conclude that, even under adverse circumstances, sequential representations contain enough structure for shallow algorithms to perform inference successfully. Algorithms that operate directly on the graph representation usually require a considerable increase in resources, but do allow
for an increase in performance also.