Summary
The paper offers a new perspective on the problem of role extraction while defining node roles based on the ideas of equitable partitions and and graph-isomorphism tests, the Weisfeiler-Leman algorithm. The paper studies two associated optimization problems (cost functions) inspired by graph isomorphism testing and provides theoretical guarantees for their solutions. To validate the approach, a novel "role-infused partition benchmark" is introduced, enabling the generation of networks where nodes possess different roles in a stochastic manner.
Strengths
(+) The paper offers a new perspective on node role extraction, focusing on equitable partitions and providing a principled stochastic notion of node roles. This approach adds to the existing methods in the field and offers a new way to define and quantify node roles in complex networks.
(+) The paper presents a quantitative definition of node roles based on equitable partitions, allowing for the numerical measurement of deviation from an exact equivalence. This provides a more nuanced understanding of node roles compared to traditional definitions.
(+) The technical aspects of the paper are thorough and detailed. Also, the technical details aeem to be correct.
(+) Numerical experiments show the effectiveness and superiority of the proposed method over a graph neural network, GIN, for three different tasks.
Weaknesses
(-) While the paper briefly mentions different categories of node role extraction approaches (graphlet-based, walk-based, and matrix-factorization-based), it does not provide a detailed comparison or analysis of how the proposed equitable partitions approach compares to these existing methods. A more rigorous comparative analysis, including performance metrics and evaluation on benchmark datasets, would strengthen the paper's contribution and demonstrate the advantages of the proposed approach.
(-) The idea of Equitable partitions for node role discovery is interesting. However, the details regarding "why this approach" makes sense is missing. There can be other ways too? Why this method should work? At a conceptual level, a more rigorous explanation related to the definition of roles based on equitable partition is missing. I think this is crucially important. In other words, the paper focuses on providing details of "designing" and approach based on EP, while leaving details of "why this is appropriate"
(-) A more thorough literature review might be needed. For instance, the following paper provides a nice simple algorithm for computing equitable partitions. (I am not sure it is better or worse; however it might be handy to have a look at it.)
- Zhang et al., "Upper and Lower Bounds for Controllable Subspaces of Networks of Diffusively Coupled Agents," IEEE Transactions on Automatic control, 2014.
Also, there is some recent work on counting subgraphs (that may define node roles based on the structural attributes of the graph), for instance,
- Hassan et al., "Computing Graph Descriptors on Edge Streams." ACM Transactions on Knowledge Discovery from Data, 2023.
(-) The paper introduces a family of cost functions to assess the quality of a role partitioning. However, it does not thoroughly discuss the selection, design, or properties of these cost functions. Providing a more in-depth exploration and analysis of the different cost functions, their properties, and how they relate to the problem of node role extraction would enhance the technical understanding of the proposed approach.
(-) It is unclear how the ground truth for the sampled adjacency matrices is computed in Experiment 1 of Section 5. Moreover, GIN is a relatively old graph neural network. There are recent methods that show better results on several downstream tasks and could have been considered for baseline comparisons. Some of these works include the work of Bouritsas et al, and Ramp\'a\v{s}ek et al, below.
- Bouritsas et al., "Improving graph neural network expressivity via subgraph isomorphism counting," IEEE Transactions on Pattern Analysis and Machine Intelligence. 2022 Feb 24;45(1):657-68.
- Ramp\'a\v{s}ek, et al., "Recipe for a general, powerful, scalable graph transformer," Advances in Neural Information Processing Systems. 2022.
Questions
(-) It is mentioned that Equitable partitions imply an upper bound on the expressivity of Graph Neural Networks while citing references [26] and [43]. There is nothing of that sort in these papers. Could you point out where such results are mentioned in the said references.
(-) As coarsest equitable partition is an important concept for the paper, an example to illustrate this concept or a proper reference to another paper is vital and missing in the draft.
(-) As mentioned in the "weakness", can you explain more rigorously the motivation for using equitable partitions for node role discovery.
(-) In Theorem 3, what is the interpretation of the parameter $\delta$ and what is the computational complexity to calculate it?
(A minor comment) There are minor grammatical errors, e.g.,
- "Thus, from any node $v$ within in the same class ..." (in is not needed).
- "This also allows for Gradient Descent approaches like e.g. GNNs." (like and e.g., are used simultaneously).
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The limitations and possibly approaches to tackle these limitations are presented in the paper.