{
  "id": "2312.08671",
  "version": "v1",
  "published": "2023-12-14T06:08:35.000Z",
  "updated": "2023-12-14T06:08:35.000Z",
  "title": "Uplifting the Expressive Power of Graph Neural Networks through Graph Partitioning",
  "authors": [
    "Asela Hevapathige",
    "Qing Wang"
  ],
  "categories": [
    "cs.LG",
    "cs.AI"
  ],
  "abstract": "Graph Neural Networks (GNNs) have paved its way for being a cornerstone in graph related learning tasks. From a theoretical perspective, the expressive power of GNNs is primarily characterised according to their ability to distinguish non-isomorphic graphs. It is a well-known fact that most of the conventional GNNs are upper-bounded by Weisfeiler-Lehman graph isomorphism test (1-WL). In this work, we study the expressive power of graph neural networks through the lens of graph partitioning. This follows from our observation that permutation invariant graph partitioning enables a powerful way of exploring structural interactions among vertex sets and subgraphs, and can help uplifting the expressive power of GNNs efficiently. Based on this, we first establish a theoretical connection between graph partitioning and graph isomorphism. Then we introduce a novel GNN architecture, namely Graph Partitioning Neural Networks (GPNNs). We theoretically analyse how a graph partitioning scheme and different kinds of structural interactions relate to the k-WL hierarchy. Empirically, we demonstrate its superior performance over existing GNN models in a variety of graph benchmark tasks.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-12-14T06:08:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "graph neural networks",
      "expressive power",
      "weisfeiler-lehman graph isomorphism test",
      "permutation invariant graph partitioning enables",
      "novel gnn architecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}