Scholarlink

In graph classification tasks, the assessment of graph isomorphism is important, leading to the recent adoption of Weisfeiler-Lehman (WL) tests within Graph Neural Network (GNN) frameworks. However, the training process of these WL-based methods is less expressive due to the capability of the WL test. Besides, the over-squashing phenomenon within GNNs leads to information distortion and limits the efficiency of Message Passing (MP). To address these two challenges, Metric Isomorphism Graph Neural Network (MIGNN) followed by a distance-based MP paradigm developed from metric space is proposed in this paper. The objective of MIGNN is to ensure that non-isomorphic graphs undergo distinct MP processes, thereby enhancing the expressive capacity of GNNs for graph classification tasks. The main contributions of our MIGNN are twofold: (1) we measure graph isomorphism based on metric space, which is theoretically proven to be powerful than 1-WL test; (2) we introduce that node distance, as measured through metric space, is crucial for identifying graph isomorphism and subsequently develop a distance-based MP paradigm. Our distance-based MP paradigm not only preserves expressivity through isomorphic testing but also effectively addresses the over-squashing problem, as validated by our theoretical analysis. The experimental results from benchmark graph classification tasks show that our proposed model surpasses other isomorphism-based graph learning methods across the majority of evaluated datasets.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

MIGNN: Exploiting Metric Isomorphism for Graph Neural Networks

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Shenghui Zhang,
  • Xuekai Wei,
  • Rongqin Chen,
  • Shunran Zhang,
  • Pak Lon Ip,
  • Zijie Zhou,
  • Zhaoqi Lu,
  • Hou U. Leong

摘要

In graph classification tasks, the assessment of graph isomorphism is important, leading to the recent adoption of Weisfeiler-Lehman (WL) tests within Graph Neural Network (GNN) frameworks. However, the training process of these WL-based methods is less expressive due to the capability of the WL test. Besides, the over-squashing phenomenon within GNNs leads to information distortion and limits the efficiency of Message Passing (MP). To address these two challenges, Metric Isomorphism Graph Neural Network (MIGNN) followed by a distance-based MP paradigm developed from metric space is proposed in this paper. The objective of MIGNN is to ensure that non-isomorphic graphs undergo distinct MP processes, thereby enhancing the expressive capacity of GNNs for graph classification tasks. The main contributions of our MIGNN are twofold: (1) we measure graph isomorphism based on metric space, which is theoretically proven to be powerful than 1-WL test; (2) we introduce that node distance, as measured through metric space, is crucial for identifying graph isomorphism and subsequently develop a distance-based MP paradigm. Our distance-based MP paradigm not only preserves expressivity through isomorphic testing but also effectively addresses the over-squashing problem, as validated by our theoretical analysis. The experimental results from benchmark graph classification tasks show that our proposed model surpasses other isomorphism-based graph learning methods across the majority of evaluated datasets.