- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This work researches how different arithmetic operations impact the complexity of GNNs for each recurrence during WL color refinement algorithm. The main takeaway is that the author shows that standard ReLU GNNs need more steps to compute WL coloring, but if we add exact multiplication, we can save a lot of steps. They propose a fixed recurrent GNN that achieves this improvement using efficient color encoding. However, on the practical side, their proposal requires extremely large numbers. To sum up, this paper proposes interesting design and highlights the tradeoff between recurrence complexity and numerical precisions in GNNs.
Critical strengths
This paper is theoretically sound and novel because it builds a clear separation in recurrence complexity between standard ReLU GNNs and multiplication GNNs for WL coloring, which give us new insights in how arithmetic operations impact the computational complexity of GNNs. This method and proposal can potentially help us to analyze models beside GNNs.
To the best of my knowledge, main theorems are correct, where I checked several proofs and I don't find problems.
Critical weaknesses
The assumption on numerical precision bothers me where the proposed method relies on exact multiplication of extremely large integers. In practice, we have finite precisions, and the assumption of very huge precision is impractical, which pose questions whether the theory can really describe the practice.
This paper measures the efficiency mainly via the number of recurrences, and the authors seem to treat the multiplication of very large integers as a constant-cost operation.
Questions for authors
Q1: Can the authors explain the practicality of their proposed multiplication GNN when precision are finite? For example, finite floating point precisions? Will their GNN achieve similar reductions in recurrence complexity under this setting?
Q2: If you consider the cost of multiplication of very large integers, what will the computational efficiency be?
2 comments
I sincerely appreciate the response from the authors; however, after considerations, I decide to maintain the score of 2.
Response on finite precision and bit complexity
Thank you for checking several proofs and for highlighting the cost-model issue. With fixed floating-point precision, the exact guarantee does not survive: the construction relies on exact no-carry integer packing and exact equality of canonical codes. More generally, our output-precision lower bound rules out a fixed-dimensional, fixed-word, unit-separated exact encoding for all graph sizes.
If precision is allowed to grow, the recurrence count can remain logarithmic, but multiplication must then be charged according to the increasing operand length. Our theorem does not imply a reduction in bit operations, communication volume, memory, or wall-clock time; the explicit upper cell may use nO(k+1)-bit states. The revised abstract, introduction, and Section 5 make this distinction prominent and directly call the result an algebraic round-complexity separation. Bounded-precision approximate fingerprints are a separate and potentially practical research direction, but they relax the exact all-graph target analyzed here.