- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
Graph coloring is a classic optimization problem in graph theory. This paper proposes a contrastive learning framework to study the k-graph coloring problem, such that the embeddings of nodes with the same color converge to the same straight line and become aligned, while the embeddings of adjacent nodes tend to be pushed apart in orthogonal directions. Theoretically, this paper proves an exact lower bound for the contrastive loss and presents the global convergence results of projection optimization under Gram parameterization and the convergence analysis of the shared encoder. Experiments on synthetic and real graphs verify the transferability of the method on different graph sizes and datasets, showing that the method can achieve low-conflict assignments but allows for a small number of monochromatic edges.
Critical strengths
-
The research approach is relatively novel. This paper transforms the relationships in graph coloring into node embedding optimization through contrastive learning, aligning the embeddings of nodes with the same color and pushing the embedding representations of adjacent nodes towards orthogonality.
-
The theoretical analysis is relatively comprehensive. This paper provides a lower bound for the contrastive loss and presents the global convergence results of projection optimization under Gram parameterization, as well as the convergence analysis of the shared encoder. The theoretical foundation is quite solid.
Critical weaknesses
-
The paper proposes embedding nodes of the same color onto a single line, with adjacent nodes embedded in orthogonal directions. However, the experiments did not measure the distance between nodes of the same color or the degree of orthogonality between adjacent nodes, thus failing to fully demonstrate that the performance stems from this geometry.
-
Although the paper emphasizes scalability, it does not provide a formal time or space complexity analysis of the entire algorithm. Actual runtime alone cannot determine how the proposed method varies with graph size, embedding dimensions, etc.
Questions for authors
-
The core mechanism of the paper is line collapse of nodes of the same color and the tendency of adjacent nodes to become orthogonal. Could the authors directly report the intra-class distance and the orthogonal directions of different classes?
-
In the ablation experiments, the authors extracted some subgraphs from Cora for training and testing. The training and testing center nodes are different, but do they share the same nodes during sampling?
-
The experiments used DSATUR coloring. Is the representation learned by the model sensitive to the quality of these supervised colorings?
-
How was the 5% conflict threshold determined? Was it the optimal value obtained experimentally or derived from theoretical analysis?
Thank you to the authors for their response. The clarifications have adequately addressed my concerns. I will therefore maintain my positive assessment of the paper.