Synergistic Graph Fusion via Encoder Embedding

In this paper, we introduce a novel approach called graph fusion embedding, designed for multi-graph embedding with shared vertex sets. Under the framework of supervised learning, our method exhibits a remarkable and highly desirable “synergistic effect”: for sufficiently large vertex size, the accuracy of vertex classification consistently benefits from the incorporation of additional graphs. We establish a solid mathematical foundation for the method, beginning with the stochastic block model for binary graphs. We rigorously prove the asymptotic behavior, establish a sufficient condition for the method to achieve asymptotic optimal classification, and demonstrate the existence of the synergistic effect. These results are then extended to a general graph model, allowing the method to be applicable to any data types with appropriate transformations, making it versatile for various applications. Our comprehensive simulations and real data experiments provide compelling evidence supporting the effectiveness of our proposed method, showcasing the pronounced synergistic effect for multiple graphs from disparate sources.