A theoretical and empirical evaluation of modularities for hypergraphs
based on reviews by salvatore citraro and 1 anonymous reviewer
Comparison of modularity-based approaches for nodes clustering in hypergraphs
Abstract
Recommendation: posted 06 March 2024, validated 08 March 2024
Cazabet, R. (2024) A theoretical and empirical evaluation of modularities for hypergraphs. Peer Community in Network Science, 100181. 10.24072/pci.networksci.100181
Recommendation
Hypergraphs, as a framework to model higher-order interactions, have attracted a lot of attention in recent years. One particularly fruitful research direction consists of transposing well-defined notions in simple graphs to this new paradigm. A difficulty, but also an interesting opportunity, of this task is that a single concept in simple graphs might correspond to multiple ones in the domain to which it is transposed. The problem has for instance been discussed for link streams in Latapy et al. (2018), for notions as simple as node neighborhoods or the notion of shortest path. In the present article (Poda and Matias 2024), Poda and Matias focus on the concept of modularity and, indeed, they identify multiple definitions of modularity for hypergraphs in the literature (Chodrow et al., 2021, Kaminski et al., 2021). The first interesting contribution is the unification of these different representations using a common framework. They can thus compare, based solely on the definitions themselves, theoretical similarities and differences between those modularities for hypergraphs.
In the second part of their contribution, they turn towards the empirical evaluation of these methods. Community detection has a long tradition of experimental articles, comparing on selected benchmarks the strengths and weaknesses of selected methods, from the seminal work from Lancichinetti and Fortunato (Lancichinetti et al., 2009), to recent works comparing, for instance, modularity methods in dynamic graphs (Cazabet et al., 2020). The authors thus point to existing implementations and start comparing them using existing benchmarks for hypergraphs (Brusa and Matias, 2022, Kaminski et al., 2023). This confrontation between theoretical definition and actual networks with varying properties allows them to identify methods that do not perform as expected. Furthermore, they do not solely focus on classification performance but also evaluate other factors such as scalability. Their findings reveal that all methods perform poorly in this aspect. These observations pave the way for future work.
To conclude, this work is a very relevant contribution to the field. One could say that the first empirical comparison of methods in a particular field is a sign that it has become mature, and that is maybe one of the conclusions to draw from this article.
References
Poda, V., & Matias, C. (2024). Comparison of modularity-based approaches for nodes clustering in hypergraphs. arXiv preprint. HAL, https://hal.science/hal-04414337v2
Chodrow, P. S., N. Veldt, and A. R. Benson (2021). Generative hypergraph clustering: From blockmodels to modularity. Science Advances 7(28), eabh1303.
https://doi.org/10.1126/sciadv.abh1303
Kaminski, B., P. Pralat, and F. Theberge (2021). Community detection algorithm using hypergraph modularity. In R. M. Benito, C. Cherifi, H. Cherifi, E. Moro, L. M. Rocha, and M. Sales-Pardo (Eds.), Complex Networks & Their Applications IX, pp. 152-163.
Lancichinetti, A., & Fortunato, S. (2009). Community detection algorithms: a comparative analysis. Physical review E, 80(5), 056117.
https://doi.org/10.1103/PhysRevE.80.056117
Latapy, M., Viard, T., & Magnien, C. (2018). Stream graphs and link streams for the modeling of interactions over time. Social Network Analysis and Mining, 8, 1-29.
https://doi.org/10.1007/s13278-018-0537-7
Cazabet, R., Boudebza, S., & Rossetti, G. (2020). Evaluating community detection algorithms for progressively evolving graphs. Journal of Complex Networks, 8(6), cnaa027.
https://doi.org/10.1093/comnet/cnaa027
Brusa, L. and C. Matias (2022). HyperSBM: Stochastic blockmodel for hypergraphs. R package, https://github.com/LB1304/HyperSBM
Kaminski, B., P. Pralat, and F. Theberge (2023). Hypergraph Artificial Benchmark for Community Detection (h-ABCD). Journal of Complex Networks 11(4), cnad028
https://doi.org/10.21203/rs.3.rs-2471638/v1
The recommender in charge of the evaluation of the article and the reviewers declared that they have no conflict of interest (as defined in the code of conduct of PCI) with the authors or with the content of the article. The authors declared that they comply with the PCI rule of having no financial conflicts of interest in relation to the content of the article.
x
Evaluation round #1
DOI or URL of the preprint: https://hal.science/hal-04414337
Version of the preprint: 1
Author's Reply, 04 Mar 2024
We would like to thank the referees for their careful reading of our work and the suggestions they made to improve this contribution. We provide a tracked version of the manuscript where the major changes have been highlighted in blue.
Response to anonymous reviewer 1:
Thank you for your time and suggestions. We carefully followed most of them as detailed hereafter:
- we removed the absolute value in the measure of error, in order to distinguish over and under estimation of ground truth modularity;
- we reported (Table 5 in the Appendix) the ground-truth modularity values (mean and standard deviations over the 25 hypergraphs generated under each pair of model/scenario). As you suspected, some close to zero values induce a larger dispersion in the relative error. This is the case in particular for IRMM algorithm. We modified some of our comments accordingly;
- We did not follow your suggestion to include a comparison with standard modularity optimization of the two-section graph because it has already been done by others. Indeed, Kumar et al. (2020) include a comparison with clique reductions methods (``We reduced the original hypergraph using a clique reduction and then applied the Louvain method and Spectral Clustering'', see page 13 in that reference).
These authors concluded that: ``It is evident that hypergraph based methods perform consistently better than their clique based equivalents. Results indicate that Zhou-Spectral and NDP-Louvain are better than Spectral and Louvain respectively'' (end of page 16 in that reference).
We thus included this important information in the manuscript (second paragraph in Section 2.3).
Response to Salvatore Citraro:
Thank you for your time and suggestions. We carefully followed most of them as detailed hereafter:
- we followed your suggestions on minor text/style modifications;
- we added the reference Lee et al. (2021) containing the description of 13 real-world hypergraph datasets;
- we mentioned at the end of the introduction other methods for node and hyperedge clustering in hypergraphs;
- we limited ourselves to hyperedges of size 3 in order to stick with reasonable computing times and also to limit the complexity of the model parametrization. This information is now added in the manuscript (section 3.1).
Decision by Remy Cazabet, posted 19 Feb 2024, validated 21 Feb 2024
Both reviewers agreed on the scientific quality of the article and on its valuable addition to the literature. They proposed a list of minor modifications and propositions of improvements.
I recommend to the authors to carefully consider those feedbacks, and to submit a new, revised version, ready to be recommended by PCI.
Reviewed by anonymous reviewer 1, 13 Feb 2024
Community detection in hypergraphs is an important theoretical and practical problem. It is hard from two dimensions:
* definition of communities (it is not obvious how the communities should be defined)
* algorithms looking for the communities (these are complex combinatorial optimization problems that require decent heuristic approaches)
The presented paper gives a review of current state of the art of these both areas and then provides a comparison of available implementations of community detection algorithms.
In my opinion the presented research is a valuable experimental contribution. The authors prove to know the subject well and planned the experiments carefully. The obtained results and the conclusions drawn are convincing.
It should be noted though that the paper does not introduce new theoretical results - it is a review paper that provides a comparison of existing tools. Still - the results are valuable since the analyzed algorithms are complex and their ranking in practice is non-obvious.
What I would recommend to add to the paper is the following:
* The measure of $error$ from page 16 might be slightly misleading. It is possible that $\hat{C}$ has a better modularity than $C^{true}$ (especially that ground truth is noisy). Therefore I think that the absolute value operator in the definition should be removed so that the results do not mix 1% over and 1% under the modularity for ground truth.
* I would also recommend to report in some table modularity for ground truth for each evaluated method. The reason is that if for some considered graphs it is close to $0$ then the reported values of $error$ could be unstable (alternatively a descriptive discussion of these values could be added).
* I also recommend to add results of optimization of the standard modularity of the two-section and star-expansion graphs as comparators (to answer the question what do we gain by using the specialized methods of modularity computation). It is likely easier to perform the analysis for two-section variant, so I think showing this would be enough. Given that the considered graphs are small it is maybe possible to solve them exactly using e.g. Bayan Algorithm (https://arxiv.org/abs/2209.04562). Alternatively a decent heuristic graph modularity optimization should be considered (Leiden or TAU, see https://academic.oup.com/pnasnexus/article/2/6/pgad180/7187731)
My recommendation for this article is posive, but I encourage the authors to consider revising the points that I have raised.
Reviewed by salvatore citraro, 15 Feb 2024
The manuscript addresses the comparison of modularity-based methods for node clustering in hypergraphs through a pipeline of analysis involving the use of synthetic benchmarks. The modularity-maximization algorithms compared belong to different criteria for measuring modularity in hypergraphs, and they are tested in different settings.
I believe the manuscript contributes significantly to the new emering literature about community detection in hypergraphs, indirectly providing the first steps towards a further order/taxonomy for node clustering methods in hypergraphs, given at least the performances on the experimental scenarios introduced here. The framework proposed by the authors appears sound and robust, and the tested scenarios assess a fair comparison between the methods.
My comments below are minor and the authors are free to discuss them to the extent they believe they could improve the quality of the manuscript:
--- I would avoid specifying "binary" in the title;
--- I would switch the order of the first three sentences in the abstract as follows: (2) "Statistical analysis and node clustering..."; (3) "In contrast to the case of graphs..."; (1) "In this work, we conducted a comparative analysis...". It should more linear and readable;
--- When reading the intro, some questions arise spontaneously, e.g., "With the emergence of hypergraph datasets...", which ones? Do the authors believe it is important to mention some of them?
--- Similarly, when reading intro, do the authors believe it is worth mentioning other methods for node clustering in hypergraphs besides the modularity-maximization ones, just for background and context? Moreover (I know it is not the focus of the article), could it be worth mentioning existing works, if they exist, that cluster hyperedges rather than nodes, as related works?
--- typo at page 4? "This graph has the same set of nodes than the hypergraph"? --> "This graph has the same set of nodes as the hypergraph";
--- Are the limitations on hyperedge size to 3 dictated by the benchmarks implementations, or are there other reasons for this constraint?
