Modularity Maximization Lifting (Graph to Hypergraph)

This is a novel lifting based on modularity maximization and community detection. This approach extends the spectral method for community detection described by Newman [1] to create a hypergraph representation that preserves the community structure of the original graph. This method is useful for preserving the global community structure of graphs, making it valuable for tasks that require understanding large-scale network organization. Examples of this are identifying functional modules in biological networks, detecting social circles in social networks, or uncovering thematic clusters in citation networks.

This approach works as follows: (1) Compute the modularity matrix B of the graph. (2) Perform spectral clustering on B to detect communities: - Compute the leading eigenvectors of B - Apply k-means clustering to these eigenvectors (3) For each node i, create a hyperedge H_i containing: - Node i itself - The k nearest neighbors of i within its detected community

This method leverages both the graph structure (through the modularity matrix) and the original node features (for nearest neighbor calculations). It's particularly suitable for cases where the global structure and community organization of the graph are important.

The modularity matrix B is defined as:

$$B_{ij} = A_{ij} - \frac{k_i k_j}{2m}$$

where A is the adjacency matrix, k_i is the degree of node i, and m is the total number of edges.

Our method extends beyond traditional bi-partitioning by allowing for the detection of multiple communities, making it adaptable to more complex network structures. The number of communities and the size of the neighborhood for hyperedge creation are adjustable parameters.

Note that due to the random initialization in the k-means clustering step, this method is non-deterministic. This can be advantageous for exploring various possible community structures in the network.

The computational complexity is approximately $O(n^2 + nk + nct)$, where n is the number of nodes, k is the number of nearest neighbors, c is the number of communities, and t is the number of k-means iterations.

[1] Newman, M. E. J. (2013). Spectral methods for network community detection and graph partitioning. Physical Review E, 88(4), 042822. https://arxiv.org/abs/1307.7729

Submission by Valentina Sánchez [@ValentinaSanchezMelchor]

From https://github.com/pyt-team/challenge-icml-2024/pull/49