Deep graph transformation for attributed, directed, and signed networks

• Published in: Knowledge and information systems 2021-06, Vol.63 (6), p.1305-1337
• Main Authors: Guo, Xiaojie, Zhao, Liang, Homayoun, Houman, Dinakarrao, Sai Manoj Pudukotai
• Format: Article
• Language: English
• Subjects: Computer Science; Consistency; Data Mining and Knowledge Discovery; Database Management; Domains; Edge joints; Grammatical aspect; Graph theory; Graphs; Information Storage and Retrieval; Information Systems and Communication Service; Information Systems Applications (incl.Internet); IT in Business; Iterative methods; Language translation; Network topologies; Nodes; Regular Paper; Regularization; Transformations (mathematics); Translation
• ISSN: 0219-1377; 0219-3116
• DOI: 10.1007/s10115-021-01553-9

Generalized from image and language translation, the goal of graph translation or transformation is to generate a graph of the target domain on the condition of an input graph of the source domain. Existing works are limited to either merely generating the node attributes of graphs with fixed topology or only generating the graph topology without allowing the node attributes to change. They are prevented from simultaneously generating both node and edge attributes due to: (1) difficulty in modeling the iterative, interactive, and asynchronous process of both node and edge translation and (2) difficulty in learning and preserving the inherent consistency between the nodes and edges in generated graphs. A general, end-to-end framework for jointly generating node and edge attributes is needed for real-world problems. In this paper, this generic problem of multi-attributed graph translation is named and a novel framework coherently accommodating both node and edge translations is proposed. The proposed generic edge translation path is also proven to be a generalization of existing topology translation models. Then, in order to discover and preserve the consistency of the generated nodes and edges, a spectral graph regularization based on our nonparametric graph Laplacian is designed. In addition, two extensions of the proposed model are developed for signed and directed graph translation. Lastly, comprehensive experiments on both synthetic and real-world practical datasets demonstrate the power and efficiency of the proposed method.