Graph Classification via Heat Diffusion on Simplicial Complexes

Abstract

In this paper, we study the graph classification problem in vertex-labeled graphs. Our main goal is to classify graphs by comparing their higher-order structures thanks to heat diffusion on their simplices. We first represent vertex-labeled graphs as simplex-weighted super-graphs. We then define the diffusion Fréchet function over their simplices to encode the higher-order network topology and finally reach our goal by combining the function values with machine learning algorithms. Our experiments on real-world bioinformatics networks show that using diffusion Fréchet function on simplices is promising in graph classification and more effective than the baseline methods. To the best of our knowledge, this is the first study in the literature using heat diffusion on higher-dimensional simplices in a graph mining problem. We believe that our method can be extended to different graph mining domains, beyond the graph classification problem.

Keywords

• Graph classification
• diffusion Fréchet function
• simplicial complex
• simplicial Laplacian operator