This paper presents an analytical study of the oversmoothing issue in diffusion-based Graph Neural Networks (GNNs). Generalizing beyond extant approaches grounded in random walk analysis or particle systems, we approach this problem through operator semigroup theory. This theoretical framework allows us to rigorously prove that oversmoothing is intrinsically linked to the ergodicity of the diffusion operator. Relying on semigroup method, we can quantitatively analyze the dynamic of graph diffusion and give a specific mathematical form of the smoothing feature by ergodicity and invariant measure of operator, which improves previous works only show existence of oversmoothing. This finding further poses a general and mild ergodicity-breaking condition, encompassing the various specific solutions previously offered, thereby presenting a more universal and theoretically grounded approach to relieve oversmoothing in diffusion-based GNNs. Additionally, we offer a probabilistic interpretation of our theory, forging a link with prior works and broadening the theoretical horizon. Our experimental results reveal that this ergodicity-breaking term effectively mitigates oversmoothing measured by Dirichlet energy, and simultaneously enhances performance in node classification tasks.

Graph Neural Networks (GNNs) learn from graph-structured data by passing messages between neighboring nodes along edges on certain topological layouts. While layouts can be essential to GNNs' performance, extant methods generally consider obtaining layouts from limited perspectives. In this paper, we introduce Distributional Edge Layouts (DELs), a first-of-its-kind method to sample a collection of topological layouts from a Boltzmann distribution under physical energies. By integrating DELs into GNNs, a wide landscape of feasible graph layouts can be captured from a holistic perspective, overcoming the intrinsic drawbacks in existing GNN designs.In practice, DELs can complement various GNN architectures with high versatility. Our theoretical analysis proves that GNNs equipped with DELs maintain at least the same expressive as their original counterparts, with empirical potential offering extra expressivity. Extensive experiments demonstrate that DELs consistently and substantially improve the performance of a wide range of GNN baselines across multiple datasets, achieving state-of-the-art results. This improvement suggests that DELs capture important distributional information previously overlooked by traditional GNN approaches. DEL is open-sourced at https://github.com/LOGO-CUHKSZ/DEL.

Scene parsing has attracted significant attention for its practical and theoretical value in computer vision. A typical scene parsing algorithm seeks to densely label pixels or 3-dimensional points from a scene. Traditionally, this procedure relies on a pre-trained classifier to identify the label information, and a smoothing step via Markov Random Field to enhance the consistency. LabelTranfer is a category of scene parsing algorithms to enhance traditional scene parsing framework, by finding dense correspondence and transferring labels across scenes. In this paper, we present a novel scene parsing algorithm which matches maximal similar structures between scenes via efficient low-rank graph matching. The inputs of the algorithm are images, and well- aligned point clouds if available. The images and the point clouds are processed in separate pipelines. The pipeline of images is to learn a reliable classifier and to match local structures via graph matching. The pipeline of point clouds is to conduct preliminary segmentation and to generate feasible label sets. The two pipelines are merged at inference step, in which we elaborate effective and efficient potential functions. We propose a new graph matching model incorporating low-rank and Frobenius regularization, which not only guarantees an accurate solution, but also provides high optimization efficiency via an eigen-decomposition strategy. Several challenging experiments are conducted, showing competitive performance of the proposed method compared to state-of-the-art LabelTransfer algorithm. Further, with point clouds, the performance can be significantly enhanced.