Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization

Haoran Zheng; Renchi Yang; Yubo Zhou; Jianliang Xu

doi:10.1145/3770854.3780307

Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization

Haoran Zheng
, Renchi Yang^*
, Yubo Zhou
, Jianliang Xu

^*Corresponding author for this work

Department of Computer Science

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

Abstract

Message passing neural networks (MPNNs) have emerged as go-to models for learning on graph-structured data in the past decade. Despite their effectiveness, most of such models still incur severe issues such as over-smoothing and -correlation, due to their underlying objective of minimizing the Dirichlet energy and the derived neighborhood aggregation operations. In this paper, we propose the DDSM, a new MPNN model built on an optimization framework that includes the stress majorization and orthogonal regularization for overcoming the above issues. Further, we introduce the diffusion distances for nodes into the framework to guide the new message passing operations and develop efficient algorithms for distance approximations, both backed by rigorous theoretical analyses. Our comprehensive experiments showcase that DDSM consistently and considerably outperforms 15 strong baselines on both homophilic and heterophilic graphs.

Original language	English
Title of host publication	KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1
Place of Publication	New York, NY, USA
Publisher	Association for Computing Machinery (ACM)
Pages	2031–2041
Number of pages	11
Volume	1
ISBN (Electronic)	9798400722585
ISBN (Print)	9798400722585
DOIs	https://doi.org/10.1145/3770854.3780307
Publication status	E-pub ahead of print - 20 Apr 2026
Event	32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining - International Convention Center Jeju, Jeju Island, Korea, Republic of Duration: 9 Aug 2026 → 13 Aug 2026 https://dl.acm.org/doi/proceedings/10.1145/3770854 (Conference proceeding) https://kdd2026.kdd.org/ (Conference website)

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Volume	1-A
ISSN (Print)	2154-817X

Conference

Conference	32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Abbreviated title	KDD 2026
Country/Territory	Korea, Republic of
City	Jeju Island
Period	9/08/26 → 13/08/26
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3770854 (Conference proceeding) https://kdd2026.kdd.org/ (Conference website)

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

User-Defined Keywords

diffusion distance
dirichlet energy
message passing
over-correlation
over-smoothing

Access to Document

10.1145/3770854.3780307

https://dl.acm.org/doi/10.1145/3770854.3780307

Cite this

Zheng, H., Yang, R., Zhou, Y., & Xu, J. (2026). Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization. In KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1 (Vol. 1, pp. 2031–2041). (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. 1-A). Association for Computing Machinery (ACM). Advance online publication. https://doi.org/10.1145/3770854.3780307

Zheng, Haoran ; Yang, Renchi ; Zhou, Yubo et al. / Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization. KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1. Vol. 1 New York, NY, USA : Association for Computing Machinery (ACM), 2026. pp. 2031–2041 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{2783c55d03a646dc825694a05825363f,

title = "Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization",

abstract = "Message passing neural networks (MPNNs) have emerged as go-to models for learning on graph-structured data in the past decade. Despite their effectiveness, most of such models still incur severe issues such as over-smoothing and -correlation, due to their underlying objective of minimizing the Dirichlet energy and the derived neighborhood aggregation operations. In this paper, we propose the DDSM, a new MPNN model built on an optimization framework that includes the stress majorization and orthogonal regularization for overcoming the above issues. Further, we introduce the diffusion distances for nodes into the framework to guide the new message passing operations and develop efficient algorithms for distance approximations, both backed by rigorous theoretical analyses. Our comprehensive experiments showcase that DDSM consistently and considerably outperforms 15 strong baselines on both homophilic and heterophilic graphs.",

keywords = "diffusion distance, dirichlet energy, message passing, over-correlation, over-smoothing",

author = "Haoran Zheng and Renchi Yang and Yubo Zhou and Jianliang Xu",

note = "This work is partially supported by the National Natural Science Foundation of China (No. 62302414), the Hong Kong RGC ECS grant (No. 22202623) and YCRG (No. C2003-23Y), Guangdong Basic and Applied Basic Research Foundation (Project No. 2023B1515130002), the Huawei Gift Fund, and Guangdong and Hong Kong Universities “1+1+1” Joint Research Collaboration Scheme, project No.: 2025A0505000002. Publisher Copyright: {\textcopyright} 2026 Copyright held by the owner/author(s).; 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2026 ; Conference date: 09-08-2026 Through 13-08-2026",

year = "2026",

month = apr,

day = "20",

doi = "10.1145/3770854.3780307",

language = "English",

isbn = "9798400722585",

volume = "1",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery (ACM)",

pages = "2031–2041",

booktitle = "KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/3770854, https://kdd2026.kdd.org/",

}

Zheng, H, Yang, R, Zhou, Y & Xu, J 2026, Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization. in KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1. vol. 1, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, vol. 1-A, Association for Computing Machinery (ACM), New York, NY, USA, pp. 2031–2041, 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Jeju Island, Korea, Republic of, 9/08/26. https://doi.org/10.1145/3770854.3780307

Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization. / Zheng, Haoran; Yang, Renchi; Zhou, Yubo et al.
KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1. Vol. 1 New York, NY, USA: Association for Computing Machinery (ACM), 2026. p. 2031–2041 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. 1-A).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization

AU - Zheng, Haoran

AU - Yang, Renchi

AU - Zhou, Yubo

AU - Xu, Jianliang

N1 - This work is partially supported by the National Natural Science Foundation of China (No. 62302414), the Hong Kong RGC ECS grant (No. 22202623) and YCRG (No. C2003-23Y), Guangdong Basic and Applied Basic Research Foundation (Project No. 2023B1515130002), the Huawei Gift Fund, and Guangdong and Hong Kong Universities “1+1+1” Joint Research Collaboration Scheme, project No.: 2025A0505000002. Publisher Copyright: © 2026 Copyright held by the owner/author(s).

PY - 2026/4/20

Y1 - 2026/4/20

N2 - Message passing neural networks (MPNNs) have emerged as go-to models for learning on graph-structured data in the past decade. Despite their effectiveness, most of such models still incur severe issues such as over-smoothing and -correlation, due to their underlying objective of minimizing the Dirichlet energy and the derived neighborhood aggregation operations. In this paper, we propose the DDSM, a new MPNN model built on an optimization framework that includes the stress majorization and orthogonal regularization for overcoming the above issues. Further, we introduce the diffusion distances for nodes into the framework to guide the new message passing operations and develop efficient algorithms for distance approximations, both backed by rigorous theoretical analyses. Our comprehensive experiments showcase that DDSM consistently and considerably outperforms 15 strong baselines on both homophilic and heterophilic graphs.

AB - Message passing neural networks (MPNNs) have emerged as go-to models for learning on graph-structured data in the past decade. Despite their effectiveness, most of such models still incur severe issues such as over-smoothing and -correlation, due to their underlying objective of minimizing the Dirichlet energy and the derived neighborhood aggregation operations. In this paper, we propose the DDSM, a new MPNN model built on an optimization framework that includes the stress majorization and orthogonal regularization for overcoming the above issues. Further, we introduce the diffusion distances for nodes into the framework to guide the new message passing operations and develop efficient algorithms for distance approximations, both backed by rigorous theoretical analyses. Our comprehensive experiments showcase that DDSM consistently and considerably outperforms 15 strong baselines on both homophilic and heterophilic graphs.

KW - diffusion distance

KW - dirichlet energy

KW - message passing

KW - over-correlation

KW - over-smoothing

UR - https://www.scopus.com/pages/publications/105038070880

U2 - 10.1145/3770854.3780307

DO - 10.1145/3770854.3780307

M3 - Conference proceeding

SN - 9798400722585

VL - 1

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 2031

EP - 2041

BT - KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1

PB - Association for Computing Machinery (ACM)

CY - New York, NY, USA

T2 - 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Y2 - 9 August 2026 through 13 August 2026

ER -

Zheng H, Yang R, Zhou Y, Xu J. Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization. In KDD 2026 - Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1. Vol. 1. New York, NY, USA: Association for Computing Machinery (ACM). 2026. p. 2031–2041. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). Epub 2026 Apr 20. doi: 10.1145/3770854.3780307

Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization

Abstract

Publication series

Conference

UN SDGs

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this