Summary
This paper proposes a new framework called the Diffusion Probabilistic Model for Structured Node Classification (DPM-SNC), which leverages diffusion probabilistic models for structured node classification on graphs. The framework aims to account for dependencies between node labels. The two key aspects of DPM-SNC are: (a) learning a joint distribution over the labels using an expressive reverse diffusion process and (b) making predictions based on known labels using manifold-constrained sampling. The authors test DPM-SNC in diverse scenarios, including partially labeled graphs in a transductive setting, as well as unlabeled graphs and in an inductive setting.
Strengths
1. The paper effectively applies probabilistic diffusion, one of the hottest techniques in the community, to the structured node classification problem.
2. DPM-SNC can be used in combination with any graph neural network (GNN) and to enhance performance on node classification tasks. This improvement is not solely empirical, as the authors provide theoretical analysis tying it to enhanced theoretical expressive power.
3. The authors conduct a comprehensive experimental evaluation, showing DPM-SNC's superior performance in both transductive and inductive node classification tasks.
Weaknesses
1. Although it is understandable that certain technical details are relegated to the appendix due to space limitations, the main paper could benefit from being more self-contained. This could be achieved by shortening the introduction or reducing some figures. Without referring to the appendix, especially for readers without expertise in diffusion models, it's difficult to grasp exactly how DPM-SNC makes predictions.
2. The paper lacks a discussion or comparison with similar works that combine deep neural networks and label propagation for structured node classification [1, 2]. These works could be used as additional baselines or in discussions related to the proposed method.
3. It appears that a limitation of the proposed method is that the diffusion process operates on (noisy versions of) labels of nodes, not their representation vectors. As a result, while DPM-SNC seems to work well for node classification problems, it's unclear whether the trained model could be effectively used as a general node embedding model for solving edge- or graph-level problems, or multi-label classification problems.
[1] Huang et al., Combining Label Propagation and Simple Models Outperforms Graph Neural Networks, ICLR 2021
[2] Yoo et al., Belief Propagation Network for Hard Inductive Semi-Supervised Learning, IJCAI 2019
Questions
1. Why did the authors exclusively use GCNII for the proposed method and not for the competitor models?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The authors have acknowledged the limitations of their approach.