Graph data represents pairwise relationships between vertices through a collection of vertices and edges. Typically, a graph (or network) is represented by an adjacency matrix A of size 𝑛 × 𝑛, where A(𝑖, 𝑗) denotes the edge weight between the 𝑖th and 𝑗th vertices. Alternatively, the graph can be stored in an edgelist E of size 𝑠 × 3, with the first two columns indicating the vertex indices of each edge and the last column representing the edge weight.
Community detection, also known as vertex clustering or graph partitioning, is a fundamental problem in graph analysis [6,8,10,13]. The primary objective is to identify natural groups of vertices where intra-group connections are stronger than inter-group connections. Over the years, various approaches have been proposed, including modularity-based methods [2,22], spectral-based methods [15,21], and likelihood-based techniques [1,7], among others.
Spectral-based and likelihood-based methods are extensively studied in the statistics community, but they tend to be computationally slow for large graphs. On the other hand, modularity-based methods are faster and widely used in practice, but they lack theoretical investigations and only provide community labels without vertex embedding. Moreover, determining the appropriate community size poses a challenge for any method and is often addressed in an ad-hoc manner or assumed to be known. Therefore, a desirable approach is to develop a method that can achieve community detection, vertex representation, and community size determination under a unified framework.
In this paper, we propose a graph encoder ensemble algorithm that simultaneously fulfills all these objectives. Our algorithm leverages a normalized one-hot graph encoder [19], ensemble learning [3,12], k-means clustering [5,11], and a novel rank-based cluster size measure called the minimal rank index. The proposed algorithm exhibits linear running time and demonstrates excellent numerical performance. The code for the algorithm is available on GitHubfoot_0 .
We begin by introducing the one-hot graph encoder embedding from [19], known for its computational efficiency and theoretical guarantees under random graph models. This embedding forms the foundation of our proposed ensemble method, outlined in Algorithm 1. The ensemble algorithm incorporates crucial enhancements, including 𝐿2 normalization, the minimal rank index, and ensemble embedding, which are elaborated in the subsequent subsections.
Given the graph adjacency matrix A ∈ R 𝑛×𝑛 and a label vector Y ∈ 1, . . . , 𝐾 𝑛 , we define 𝑛 𝑘 as the number of observations per class, where
for 𝑘 = 1, . . . , 𝐾. We construct the one-hot encoding matrix W ∈ R 𝑛×𝐾 on Y, then normalize it by the number of observations perclass. Specifically, for each vertex 𝑖 = 1, . . . , 𝑛, we set
if and only if Y 𝑖 = 𝑘, and 0 otherwise. The graph encoder embedding is then obtained by performing a simple matrix multiplication:
Each row Z(𝑖, :) represents a 𝐾-dimensional Euclidean representation of vertex 𝑖. The computational advantage of the graph encoder embedding lies in the matrix multiplications, which can be efficiently implemented by iterating over the edge list E only once, without the need for the adjacency matrix [19]. In Algorithm 1, we denote the above steps as Z = one-hot-emb(E, Y).
The proposed ensemble method is described in detail in Algorithm 1. It can be applied to binary or weighted graphs, as well as directed or undirected graphs. Throughout this paper, we set the number of random replicates 𝑟 = 10, the maximum number of iterations 𝑚 = 20, and the clustering range is determined based on the specific experiment.
In the pseudo-code, the 𝐿2 normalization step is represented by Z = normalize(Z), which normalizes each vertex representation to have unit norm (see Section 2.3 for more details). Additionally, given an embedding Z and a label vector Y, the minimal rank index is denoted as MRI(Z, Y) ∈ [0, 1], which measures the quality of clustering with a lower value indicating better clustering (details in Section 2.4). The k-means clustering step is denoted as k-means(Z, 𝐾), and the adjusted Rand index is denoted as ARI(Y, Y 2 ), which measures the similarity between two label vectors of the same size. The ARI is a popular matching metric that ranges from -∞ to 1, with a larger positive value indicating better match quality and a value of 1 representing a perfect match [14].
Require: An edgelist E, a range of potential cluster size 𝑅, number of random replicates 𝑟 , and number of maximum iteration 𝑚. Ensure: The graph embedding Z ∈ R 𝑛× K for all vertices, the estimated number of clusters K, the cluster indices
and the minimal rank index 𝑖𝑛𝑑 ∈ [0, 1]. function Graph-Encoder-Ensemble(E, 𝑅, 𝑟, 𝑚) 𝑖𝑛𝑑 = 1; ⊲ initialize the index to pick best cluster size for 𝑘 ∈ 𝑅 do 𝑖𝑛𝑑 2 = 1; ⊲ initialize the index to pick best random replicate for 𝑖 = 1, . . . , 𝑟 do Ŷ𝑘 = 𝑟𝑎𝑛𝑑 (𝑘, 𝑛); ⊲ randomly initialize a label vector of length 𝑛 in [𝑘]
The normalization step in Algorithm 1 scales each vertex embedding to unit norm. Specifically, for each vertex 𝑖,
if ∥Z(𝑖, :)∥2 > 0. The normalization step plays a crucial role in achieving improved clustering results, as demonstrated in Figure 1 using a sparse random graph model with two communities. The normalized embedding is represented on a unit sphere, effectively capturing the connectivity information while mitigating the influence of vertex degrees. In contrast, the un-normalized embedding is significantly affected by the original vertex degrees, resulting in vertices from the same community being widely dispersed. This distinction bears resemblance to the two-truth phenomenon observed in graph adjacency and graph Laplacian, where the Laplacian spectral embedding (LSE) can be seen as a degree-normalized version of the adjacency spectral embedding (ASE). The LSE typically performs better on sparse graphs. Further numerical evaluations on the normalization effect can be found in Section 3.2 and Table 1.
We introduce a new rank-based measure called the minimal rank index (MRI) to assess the quality of clustering. This measure plays a crucial role in Algorithm 1 as it enables the comparison of multiple embeddings generated from different initializations and community sizes.
Given the cluster index Y𝑖 of vertex 𝑖, the Euclidean distance function 𝑑 (•, •), and the mean of the 𝑘th cluster denoted as
the minimal rank index is computed as:
The MRI measures how often the vertex embedding is not closest to its corresponding cluster mean. A smaller MRI value indicates better clustering quality, with MRI equal to 0 indicating that every vertex is closest to its cluster mean. In the context of k-means clustering, MRI is non-zero when the k-means algorithm fails to converge.
In comparison to common cluster size measures such as Silhouette Score, Davies-Bouldin index, Variance Ratio Criterion, and Gap criterion [4,16], MRI is rank-based rather than based on actual distances. These other measures compute ratios of within-cluster distances to between-cluster distances. If any of these measures were used in Algorithm 1 instead of MRI, the choice of cluster size would be biased towards the smallest possible value. This is due to the incremental nature of graph encoder embedding in Algorithm 1, where the embedding dimension is equal to the community size 𝑘. Consequently, within-cluster distances become smaller for smaller values of 𝑘, resulting in a bias towards the smallest 𝑘 when using actual distance.
Ensemble learning is utilized in Algorithm 1 to improve learning performance and reduce variance by employing multiple models.
The approach can be summarized as follows: for each value of 𝑘 in the cluster range, we generate a set of vertex embeddings and community labels using random label initialization. The model with the smallest MRI is selected as the best model. In cases where multiple models have the same smallest MRI, the average embedding is used.
Additionally, among all possible choices of cluster size 𝑘, the best embedding with the smallest MRI is selected. If there are multiple embeddings with the same smallest MRI, the one with the largest 𝑘 is chosen. For instance, if the MRI values are 0, 0, 0, 0.1, 0.2 for 𝐾 = 2, 3, 4, 5, 6, the graph encoder ensemble would select K = 4.
Algorithm 1 comprises several steps, including one-hot graph encoder embedding, k-means clustering, MRI computation, and ensembles. Let 𝑛 be the number of vertices and 𝑠 be the number of edges. At any fixed 𝑘, the one-hot graph encoder embedding takes 𝑂 (𝑛𝑘 + 𝑠), k-means takes 𝑂 (𝑛𝑘), and the MRI computation takes 𝑂 (𝑛𝑘). Therefore, the overall time complexity of Algorithm 1 is 𝑂 (𝑟𝑚(𝑛 max(𝑅) + 𝑠), which is linear with respect to the number of vertices and edges. The storage requirement is also 𝑂 (𝑛 max(𝑅) +𝑠). In practical terms, the graph encoder ensemble algorithm exhibits remarkable efficiency and scalability. Testing on simulated graphs with default parameters and max(𝑅) = 10, it takes less than 3 minutes to process 1 million edges and less than 20 minutes for 10 million edges.
In this section, we conduct extensive numerical experiments to demonstrate the advantages of the graph encoder ensemble, as well as the individual benefits of normalization, ensemble, and MRI. We compare these approaches against benchmarks including the algorithm without normalization, without ensemble, with MRI replaced, and using adjacency/Laplacian spectral embedding. The performance is evaluated using the adjusted Rand index (ARI), which measures the degree of agreement between the estimated communities and the ground-truth labels.
The stochastic block model (SBM) is a widely used random graph model for studying community structure [9,20]. Each vertex 𝑖 is associated with a class label 𝑌 𝑖 ∈ {1, . . . , 𝐾 }. The class label may be fixed a-priori, or generated by a categorical distribution with prior probability {𝜋 𝑘 ∈ (0, 1) with 𝐾 𝑘=1 𝜋 𝑘 = 1}. Then a block probability matrix B = [B(𝑘, 𝑙)] ∈ [0, 1] 𝐾 ×𝐾 specifies the edge probability between a vertex from class 𝑘 and a vertex from class 𝑙. For any 𝑖 < 𝑗,
The degree-corrected stochastic block model (DC-SBM) [23] is a generalization of SBM to better model the sparsity of real graphs. Everything else being the same as SBM, each vertex 𝑖 has an additional degree parameter 𝜃 𝑖 , and the adjacency matrix is generated by
In our simulations, we consider three DC-SBM models with increasing community sizes. In all models, the degrees are generated randomly by 𝜃 𝑖 𝑖.𝑖.𝑑.
∼ 𝐵𝑒𝑡𝑎 (1,4). Simulation 1: 𝑛 = 3000, 𝐾 = 2, 𝑌 𝑖 = {1, 2} equally likely, and the block probability matrix is
Simulation 2: 𝑛 = 3000, 𝐾 = 4, 𝑌 𝑖 = {1, 2, 3, 4} with prior probability [0.2, 0.2, 0.3, 0.3], and the block probability matrix is
Simulation 3: 𝑛 = 3000, 𝐾 = 5, 𝑌 𝑖 with equally likely prior probability, and the block probability matrix satisfies B(𝑖, 𝑖) = 0.2 and B(𝑖, 𝑗) = 0.1 for all 𝑖 = 1, . . . , 5 and 𝑗 ≠ 𝑖.
Table 1 provides clear evidence of the superior clustering performance achieved by the normalized algorithm compared to the unnormalized algorithm. To isolate the impact of normalization, we set 𝑟 = 1 and assume the cluster size is known. The observed improvement aligns with the phenomenon observed between adjacency spectral embedding (ASE) and Laplacian spectral embedding
In this simulation, we assume a known cluster size and conduct 100 Monte Carlo replicates to compare the performance of the ensemble algorithm (𝑟 = 10) with the no-ensemble version (𝑟 = 1). The results in Table 2 clearly demonstrate the superiority of the ensemble algorithm: it achieves higher mean ARI and significantly reduces the variance compared to the no-ensemble version. Based on our empirical observations, the default choice of 𝑟 = 10 yields satisfactory results across our experiments. Additionally, if the graph size is sufficiently large and the community structure is wellseparated, using a smaller value of 𝑟 or even 𝑟 = 1 is sufficient. This is evident in simulation 1 of Table 2
In this analysis, we explore the performance of the algorithm in estimating the community size. Instead of using the ground-truth size, we consider a range of potential sizes from 𝑅 = 2 to 𝑅 = 10, and the results are presented in Figure 2. These findings provide insights into the performance of the algorithm in accurately estimating the community size and highlight the importance of the MRI measure in achieving accurate size determination. In the right panel, the average Silhouette Score is computed as an alternative size measure, which is biased towards smaller community sizes and chooses K𝑆𝑆 = 2, resulting in a different estimation compared to the ground-truth size.
This paper introduces the graph encoder ensemble, which achieves graph embedding, community detection, and community size determination in a unified framework. Its main advantages include ease of implementation, computational efficiency, and excellent performance in community detection and community size selection. Several potential future directions include exploring mathematical proofs for asymptotic clustering optimality, investigating theoretical properties of MRI, and extending the method to dynamic and multi-modal graphs [17,18].
https://github.com/cshen6/GraphEmd