A Regularized Wasserstein Framework for Graph Kernels

Asiri Wijesinghe, Qing Wang, Stephen Gould

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    1 Citation (Scopus)


    We propose a learning framework for graph kernels, which is theoretically grounded on regularizing optimal transport. This framework provides a novel optimal transport distance metric, namely Regularized Wasserstein (RW) discrepancy, which can preserve both features and structure of graphs via Wasserstein distances on features and their local variations, local barycenters and global connectivity. Two strongly convex regularization terms are introduced to improve the learning ability. One is to relax an optimal alignment between graphs to be a cluster-to-cluster mapping between their locally connected vertices, thereby preserving the local clustering structure of graphs. The other is to take into account node degree distributions in order to better preserve the global structure of graphs. We also design an efficient algorithm to enable a fast approximation for solving the optimization problem. Theoretically, our framework is robust and can guarantee the convergence and numerical stability in optimization. We have empirically validated our method using 12 datasets against 16 state-of-the-art baselines. The experimental results show that our method consistently outperforms all state-of-the-art methods on all benchmark databases for both graphs with discrete attributes and graphs with continuous attributes.

    Original languageEnglish
    Title of host publicationProceedings - 21st IEEE International Conference on Data Mining, ICDM 2021
    EditorsJames Bailey, Pauli Miettinen, Yun Sing Koh, Dacheng Tao, Xindong Wu
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Number of pages10
    ISBN (Electronic)9781665423984
    Publication statusPublished - 2021
    Event21st IEEE International Conference on Data Mining, ICDM 2021 - Virtual, Online, New Zealand
    Duration: 7 Dec 202110 Dec 2021

    Publication series

    NameProceedings - IEEE International Conference on Data Mining, ICDM
    ISSN (Print)1550-4786


    Conference21st IEEE International Conference on Data Mining, ICDM 2021
    Country/TerritoryNew Zealand
    CityVirtual, Online


    Dive into the research topics of 'A Regularized Wasserstein Framework for Graph Kernels'. Together they form a unique fingerprint.

    Cite this