Balanced Multi-Relational Graph Clustering

Authors: zhixiang  shen
haolan  he
zhao  kang
Venue: acmmm_org_ACMMM_2024_Conference
Published: 2024-04-07 14:51:32

Abstract: Multi-relational graph clustering has demonstrated remarkable success in uncovering underlying patterns in complex networks. Representative methods manage to align different views motivated by advances in contrastive learning. Our empirical study finds the pervasive presence of imbalance in real-world graphs, which is in principle contradictory to the motivation of alignment. In this paper, we first propose a novel metric, the Aggregation Class Distance, to empirically quantify structural disparities among different graphs. To address the challenge of view imbalance, we propose Balanced Multi-Relational Graph Clustering (BMGC), comprising unsupervised dominant view mining and dual signals guided representation learning. It dynamically mines the dominant view throughout the training process, synergistically improving clustering performance with representation learning. Theoretical analysis ensures the effectiveness of dominant view mining. Extensive experiments and in-depth analysis on real-world and synthetic datasets showcase that BMGC achieves state-of-the-art performance, underscoring its superiority in addressing the view imbalance inherent in multi-relational graphs. The source code and datasets are available at https://github.com/zxlearningdeep/BMGC.

Main paper: 
 introduction: 
 Multi-relational graphs, which involve a set of nodes with multiple relations, are prevalent in the real world because of their extraordinary ability in characterizing complex systems [29] . Some typical instances are citation networks, social networks, and knowledge graphs [24, 38] . Recently, the unsupervised exploration of the inherent pattern in complex networks has attracted considerable attention, particularly in the context of multiview graph clustering (MVGC). Conventional MVGC techniques typically combine graph optimization with clustering techniques such as subspace clustering and spectral clustering [13, 22] . With the advancement of Graph Neural Networks (GNNs), a new wave of deep MVGC methods has been proposed, such as O2MAC [5] , DMGI [25] , HDMI [11] , BTGF [28] . They have demonstrated significant efficacy.However, representative MVGC methods often align all views to seek consistent information with the aid of a contrastive learning mechanism [11, 20, 28, 36] . This approach often ignores the fact that different views in real-world data do not always carry equal significance, i.e., the imbalance phenomenon. Our empirical analysis of real-world multi-relational graphs confirms this intuition. As shown in Fig. 1 , different relations exhibit a big gap in classification accuracy. Therefore, naively aligning different views could degrade the final performance.To this end, we address the view imbalance problem in multirelational graphs in this work. Unlike other multiview data, the view differences in multi-relational graphs are rooted in their topology structures. Thus, a natural question arises: (Q1) How can we quantify the structural disparities between views in multirelational graphs? Previous studies in multimodal learning indicate the presence of a dominant view in view-imbalanced data [34] . Given the clustering tasks, another question appears: (Q2) How can we discover the dominant view without supervision to guide multi-relational graph clustering?In addressing Q1, we propose a simple yet effective view evaluation metric: Aggregation Class Distance (ACD). Unlike previous methods that solely calculate graph homophily ratios at the edge or node level [23] , ACD takes into account both the aggregation process and the distribution of node classes. Empirical studies conducted on real-world datasets demonstrate the efficacy of this novel metric in evaluating the quality of views in multi-relational graphs.For Q2, we propose Balanced Multi-Relational Graph Clustering (BMGC), which incorporates unsupervised dominant view mining and dual signal guided representation learning. A dynamic method of unsupervised exploration of the dominant view is employed throughout the training process, taking advantage of view-specific representations and original node features. Theoretical analysis establishes the connection between this approach and ACD, ensuring the effectiveness of dominant view mining. Afterward, dual signals from the dominant view and node features supervise the graph embedding, promoting co-aligned representation learning. Finally, the dominant assignment is utilized to further enhance the clustering performance. In particular, dynamic extraction of the dominant view coupled with representation learning synergistically boosts model training.We underscore the primary contributions of this study as follows:• We explore view imbalance in multi-relational graphs and design a metric for evaluating view quality. Our empirical study confirms the presence of view disparities and validates the utility of our proposed metric. • To our best knowledge, we are the first to tackle view imbalance in multi-relational graphs without supervision. BMGC integrates an unsupervised method for dominant view mining and dual signal guided representation learning. Furthermore, the dominant assignment is leveraged to facilitate self-training clustering. A theoretical guarantee is provided to demonstrate the efficacy of our approach. • We conduct comprehensive experiments and in-depth analysis on real-world and synthetic datasets. BMGC surpasses existing advanced methods across all datasets, affirming its effectiveness and superiority in addressing view imbalance. 
related work 2.1 multiview graph clustering: 
 Recently, there have been extensive explorations into multiview graph clustering. Typical shallow methods, such as MvAGC [13] and MCGC [22] , combine graph filtering with self-expression learning to leverage attribute and structural information simultaneously. With the progress in representation learning, several deep methods have emerged. Most of them start by unsupervised learning of node representations and then apply the k-means algorithm on these representations to obtain clustering results. O2MAC [5] is the first to employ GNN for MVGC, selecting the most informative view as input and reconstructing the graph structures of all views to capture shared information. Although O2MAC considers discrepancies in different graph structures, its encoding strategy, which retains only the best view, results in degradation into a single-view method. Moreover, it uniformly reconstructs the graph structures of all views, which in turn disregards the view imbalance, further leading to suboptimal results. DMGI [25] and HDMI [11] optimize embeddings by maximizing mutual information between local and global representations. MGCCN [15] , MGDCR [20] , and BTGF [28] incorporate various contrastive losses to achieve the alignment of the representation and prevent dimension collapse. DuaLGR [14] extracts supervised signals from node attributes and graph structures to guide the MVGC. CoCoMG [26] and DMG [21] approach multi-view representation learning from the perspectives of consistency and complementarity. Although numerous methods achieve representation learning through multiview alignment, most of them overlook the inherent performance disparities between different views. These alignment-based methods tend to treat all graphs equally, which compromises the quality of node representations and thereby deteriorates the clustering results.In supervised or semi-supervised tasks, methods like HAN [35] and SSAMN [30] consider the varying importance of views. However, they require labeled information for training, which is unsuitable for unsupervised tasks. To our best knowledge, we are the first to address view imbalance in multiview graph clustering.Numerous efforts have been dedicated to addressing the challenges of imbalanced multiview learning from diverse perspectives. Works such as [8, 16] tackle imbalanced views through decision-level fusion. Specifically, they initially cluster each view and then fuse the view-specific clustering results. Another distinct avenue involves leveraging similarity graphs. MDcR [40] constructs balanced view-specific inter-instance similarity graphs, utilizes embedding techniques to acquire latent representations, and concatenates them to form the final representation for clustering. In contrast, FMUGE [39] takes a different approach to model order, initially combining view-specific similarity matrix to create a common similarity graph, followed by learning a comprehensive multiview representation. However, all of these methods cannot handle graph structure data.Imbalanced multimodal learning has also attracted widespread attention. Recent theoretical advancements have demonstrated the potential of multimodal learning to surpass the upper limits of single-modal performance [10] . However, due to the varying confidence levels and noise across different modalities, the learning process is susceptible to inducing bias towards a dominant modality. To achieve a balanced multimodal classification, OGM [27] devises a modality-wise difference ratio to monitor the contribution discrepancy of each modality to the target, thus adaptively adjusting the gradients of each modality. Subsequently, PMR [6] proposes Prototypical Modality Rebalance, accelerating the slow-learning modality by enhancing its clustering towards prototypes. Despite the effectiveness of these methods, none have considered graph data. Therefore, methods to handle the view imbalance in the realm of unsupervised multiview graph learning are urgently needed. 
empirical study: 
 Notation. In this work, we define a multi-relational graph asG = {V, E 1 , • • • , E 𝑣 , • • • , E 𝑉 , 𝑋 },where V is the node set with 𝑁 nodes and E 𝑣 is the edge set in the 𝑣-th view. 𝑉 > 1 is the number of relational graphs. 𝑋 ∈ R 𝑁 ×𝑑 𝑓 is the feature matrix and 𝑥 ∈ R 𝑁 is a column of the feature matrix that represents a graph signal. Ã𝑣 denotes the original adjacency matrix of the 𝑣-th view.𝐷 𝑣 represents the degree matrix. The normalized adjacency matrix of the 𝑣-th view is given by 𝐴 𝑣 = (𝐷 𝑣 ) -1 2 Ã𝑣 (𝐷 𝑣 ) -1 2 . It is a wellknown fact that the eigenvalues of 𝐴 𝑣 in each view are contained within [-1, 1]. Â𝑣 = (𝐷 𝑣 + 𝐼 ) -1 2 ( Ã𝑣 + 𝐼 )(𝐷 𝑣 + 𝐼 ) -1 2 represents the normalized adjacency matrix with a self-loop to each node, where 𝐼 is an identity matrix. 𝐶 is the number of node classes, and 𝑦 ∈ R 𝑁 denotes the label vector.In a multi-relational graph, the imbalance between views stems from differences in graph structure: some graphs contain more task-relevant information, while others are less task-relevant. Previous research has analyzed the impact of the graph structure on GNN from the perspective of graph homophily, suggesting that structures with high homophily ratios often exhibit superior performance [3, 42] . Here, the edge-level homophily ratio (ℎ𝑟 ) is definedas ℎ𝑟 = 1 | E | (𝑖,𝑗 ) ∈ E 1(𝑦 𝑖 = 𝑦 𝑗 ), where 1(•) is the indicator function that equals 1 if its argument is true and 0 otherwise. However, recent studies have shown that neighbors of different classes may not necessarily make the nodes indistinguishable [19] . Graph structure analysis should consider node neighborhood patterns and the aggregation process. To quantify structural disparities across different views, we propose a simple yet effective metric: Aggregation Class Distance (ACD). ACD evaluates structure quality based on aggregated feature distribution of node classes, adapting better to real-world complexity than assuming a direct correlation between homophily ratio and task performance. The theoretical analysis in Section 5 substantiates this assertion. We choose the Simple Graph Convolution (SGC) as the aggregation method [37] , a widely used representative aggregation operation [3, 19] . The ACD is defined as follows.Definition 1. The aggregation class distance for the 𝑣-th view, denoted as 𝑑𝑖𝑠 𝑣 , is calculated as:EQUATIONwhere 𝑁 𝑚 is the number of nodes in class 𝑚 and 𝐾 denotes the radius of aggregation. The reciprocal of 2 𝐶 2 -𝐶 represents the computation count for pairwise inter-class distances.𝑚 represents the centroid of aggregated features for nodes with class 𝑚 in the 𝑣-th view. The metric 𝑑𝑖𝑠 𝑣 gauges the inter-class distance of aggregated features. A higher value indicates better discriminability among different classes.To demonstrate the connection between ACD and view performance, we conduct empirical research on real-world datasets. We randomly select 30% of the nodes as the training set, leaving the remaining ones for the test set. The aggregation radius is set to 3, aligning with the common layer count of many GNN models [2] . A linear layer serves as the classifier. As shown in Fig. 1 , the line represents the classification accuracy of each view, while the bar chart indicates the corresponding ACD. Different views yield different results, affirming the existence of view imbalance. In each dataset, the performance of one view significantly exceeds that of others, and we refer to it as the dominant view. Furthermore, views with higher ACD values exhibit better classification results, underscoring the efficacy of ACD in gauging structural disparities between views. This empirical evidence supports the notion that ACD serves as a valuable metric for evaluating the quality of views in multi-relational graphs. It is worth noting that ACD uses node labels to assess the graph structure quality of each view, meaning that it is a supervised approach and cannot be directly applied to unsupervised learning tasks like clustering. 
methodology: 
 In this section, we propose Balanced Multi-Relational Graph Clustering, as depicted in Fig. 2 , to overcome inherent view imbalance.Unlike most GNN-based approaches [20, 21] , we decouple graph propagation and dimensionality reduction to improve scalability. Initially, we perform propagation on the node features separately for each view, acquiring view-specific aggregated features. Similarly to the approximate personalized propagation in [4] , we introduce the features of the original node as a teleport vector in each layer of the propagation process:𝑋 𝑣,0 = 𝑋, 𝑋 𝑣,𝑘+1 = (1 -𝛼) Â𝑣 𝑋 𝑣,𝑘 + 𝛼𝑋(3) where 𝑋 acts as both the starting matrix and the teleport set for each view. The hyper-parameter 𝛼 ∈ [0, 1] represents the teleport probability. 𝑘 ∈ [0, 𝐾 -1] and the aggregated features 𝑋 𝑣 = 𝑋 𝑣,𝐾 . These features are then fed into a shared encoder for dimensionality reduction:EQUATIONwhere 𝑍 𝑣 ∈ R 𝑁 ×𝑑 𝑟 denotes node representations in the 𝑣-th view. This decoupled setup avoids the time-consuming graph convolution operations during training. Subsequently, the representations for each view are fed into a shared decoder for the reconstruction of view-specific aggregated features. Effective training of each view is ensured by optimizing the reconstruction cosine error:EQUATIONEQUATIONwhere the encoder 𝑓 Θ (•) and the decoder 𝑔 Θ (•) are both implemented using a Multilayer Perceptron (MLP) in this study.Due to the absence of label information, we cannot directly utilize ACD for the assessment of view quality in multi-relational graph clustering. Therefore, grounded in the principle of invariance in the distribution of similarity between instances, we propose an unsupervised method for dominant view mining:EQUATION)where 𝑣 * denotes the dominant view. The above expression quantifies the discrepancy between the similarity matrices of original features and view-specific aggregated features, henceforth referred to as the "unsupervised metric". Therefore, the dominant view should optimally maintain instance similarities. In Section 5, we theoretically establish the effectiveness of our approach.Considering potential noise in real-world data, we refrain from directly using aggregated features to gauge view quality and, instead, rely on node representations:𝑣 * = arg min 𝑣 ∥𝑋𝑋 ⊤ -𝑍 𝑣 (𝑍 𝑣 ) ⊤ ∥ 2 𝐹 (8)In the training process, we initialize the dominant view using Equation (7) and recalculate it every 𝑡 epochs using Equation (8) . As training progresses, the quality of node representations improves, thereby bolstering the reliability of dominant view mining. Simultaneously, the dominant view would guide representation learning, as elaborated later. It constitutes a mutually reinforcing process.After determining the dominant view, we use it to improve the representation quality. We employ contrastive learning to align the representations of other views with the dominant view. The representations of each view are projected to a shared latent space using separate learnable MLPs for fair similarity measurement and loss calculation. The contrastive loss is defined as follows:EQUATIONwhere Z 𝑣 𝑖 is the non-linear projection of 𝑍 𝑣 𝑖 . 𝑠𝑖𝑚(•) refers to the cosine similarity and 𝜏 is the temperature parameter. The loss for aligning with the dominant view is given by:EQUATIONEach view, along with the supervision from the dominant view, should also preserve a consistent similarity distribution among the nodes. Hence, we introduce a loss to ensure alignment with the node features:L 𝐴𝑁 𝐹 = 1 𝑁 2 𝑉 𝑉 ∑︁ 𝑣=1 ∥𝑋𝑋 ⊤ -𝑍 𝑣 (𝑍 𝑣 ) ⊤ ∥ 2 𝐹 (11)Note that the loss L 𝐴𝑁 𝐹 shares a similar form with the unsupervised metric proposed in Section 4.2. This establishes a foundation for ensuring the reliability of our approach in continuously mining the dominant view during training. Ultimately, guided by dual signals from both the dominant view and node features, we accomplish the co-aligned representation learning:EQUATIONMost deep clustering methods leverage target distribution and soft cluster assignment probability distributions to achieve a selftraining clustering scheme, with the cluster distribution typically obtained by applying k-means [17, 28, 31] . To improve the clustering performance, we substitute representation distributions in other views with cluster assignments derived from the dominant view. Specifically, we apply k-means to the representations of the dominant view to obtain the dominant assignment:EQUATION) Then, the soft assignment distribution 𝑄 𝑣 in the 𝑣-th view can be formulated as:EQUATIONwhere 𝑁 𝑗 denotes the number of nodes with the cluster assignment 𝑗 and 𝑞 𝑣 𝑖 𝑗 is measured using Student's t-distribution to denote the similarity between representation 𝑍 𝑣 𝑖 and the clustering center 𝜎 𝑣 𝑗 . The target distribution 𝑃 𝑣 is computed as:EQUATION)We minimize the KL divergence between the distributions 𝑄 𝑣 and 𝑃 𝑣 for each view to enhance cluster cohesion. The final node repre-sentation 𝑍 = [𝑍 1 , • • • , 𝑍 𝑉 ] ∈ R 𝑁 ×𝑉 𝑑 𝑟 is obtained by concatenat-ing representations from all views. We simultaneously minimize the KL divergence between the 𝑄 and 𝑃 distributions of the final representation 𝑍 :EQUATIONThe overall objective of BMGC, which we aim to minimize through the gradient descent algorithm, consists of three loss terms:EQUATIONFor large-scale datasets, our method, which benefits from scalable graph encoding, eliminates the need for neighbor sampling during the training process. Consequently, we can directly perform mini-batch training, where all loss terms are computed solely from nodes within the batch. 
theoretical analysis: 
 In this section, we use a synthetic network to theoretically demonstrate the efficacy of BMGC in extracting the dominant view. For simplicity, we adopt SGC as the feature aggregation method.Data Assumption. A multi-relational graph 𝐺 has 𝑁 nodes partitioned into 2 equally sized communities 𝐶 1 and 𝐶 2 . Let 𝑐 1 , 𝑐 2 ∈ {0, 1} 𝑁 be indicator vectors for membership in each community, that is, the 𝑗 𝑡ℎ entry of 𝑐 𝑖 is 1 if the 𝑗 𝑡ℎ node is in 𝐶 𝑖 and 0 otherwise. 𝐺 has 𝑉 views, each is generated by SBM [1] , with intra-and intercommunity edge probabilities 𝑝 𝑣 and 𝑞 𝑣 . 𝐺 is such a graph model with a feature matrix 𝑋 = 𝐹 + 𝐻 ∈ R 𝑁 ×𝑑 𝑓 , where each column of 𝐻 follows a zero-centered, isotropic Gaussian noise distribution N (0, 𝜎 2 𝐼 ) and these columns are mutually independent. The matrix𝐹 is defined as 𝐹 = 𝑐 1 𝜇 ⊤ 1 + 𝑐 2 𝜇 ⊤ 2 ,where 𝜇 1 , 𝜇 2 ∈ R 𝑁 has the same Euclidean norm ∥𝜇 ∥, representing the expected characteristic vector of each community. In addition, let μ = 1 2 (𝜇 1 + 𝜇 2 ) be the average of the feature vector means. Lemma 1. Let 𝑋 𝑣 be the aggregated feature matrix of the 𝑣-th view by applying SGC, with the number of hops 𝐾, to the expected adjacency matrix Ã𝑣 and the feature matrix 𝑋 . Then,𝑋 𝑣 = 𝐹 𝑣 + 𝑐 1 (𝜃 𝑣 1 ) ⊤ + 𝑐 2 (𝜃 𝑣 2 ) ⊤ , where 𝐹 𝑣 = (𝜆 𝑣 2 ) 𝐾 𝐹 + (1 -(𝜆 𝑣 2 ) 𝐾 )(1 μ⊤ ), 𝜃 𝑣 1 and 𝜃 𝑣 2 ∈ R 𝑑 𝑓 are both distributed according to N (0, 1 𝑁 (1 + (𝜆 𝑣 2 ) 2𝐾 )𝜎 2 𝐼 ), and 𝜆 𝑣 2 = 𝑝 𝑣 -𝑞 𝑣 𝑝 𝑣 +𝑞 𝑣 ∈ [-1, 1]is the second largest non-zero eigenvalue of the associated normalized adjacency matrix 𝐴 𝑣 . Theorem 1. Let X 𝑣 1 and X 𝑣 2 denote the centroid of aggregated features for each community in the 𝑣-th view. Then, E X 𝑣 1 -X 𝑣 2 = (𝜆 𝑣 2 ) 𝐾 (𝜇 1 -𝜇 2 ) and E 𝑋𝑋 ⊤ -𝑋 𝑣 (𝑋 𝑣 ) ⊤ = 1-(𝜆 𝑣 2 ) 2𝐾 2 (∥𝜇 ∥ 2 -𝜇 ⊤ 1 𝜇 2 ) (𝑐 1 𝑐 ⊤ 1 + 𝑐 2 𝑐 ⊤ 2 -𝑐 1 𝑐 ⊤ 2 -𝑐 2 𝑐 ⊤ 1 ) + 𝜔 (𝜎 2 ), where 𝜔 (𝜎 2 ) represents the sum of terms containing 𝜎 2 that are of negligible magnitude.When negligible terms are ignored, it becomes clear that the unsupervised identification of the dominant view essentially corresponds to the view with the maximum (𝜆 𝑣 2 ) 2 . Additionally, under this data assumption, 𝑑𝑖𝑠 𝑣 = ∥ X 𝑣 1 -X 𝑣 2 ∥ indicates that a view with a larger (𝜆 𝑣 2 ) 2 is more likely to exhibit a larger ACD. Specifically, the consistent changes in both 𝑑𝑖𝑠 𝑣 and ∥𝑋𝑋 ⊤ -𝑋 𝑣 (𝑋 𝑣 ) ⊤ ∥ 2 𝐹 related to (𝜆 𝑣 2 ) 2 reveal that the identified dominant view is the one with the largest ACD value.The theoretical findings are interpretable. 𝜆 𝑣 2 is influenced by the ratio of intra-to inter-community edge probabilities, essentially measuring the homophily level of the graph structure in the 𝑣-th view. It tends toward 1 for complete homophily and -1 for complete heterophily. In both cases where (𝜆 𝑣 2 ) 2 approaches 1, there would be no confusion between nodes from different communities. For example, when 𝜆 𝑣 2 = -1, if 𝐾 is odd, feature exchange occurs between the two communities after aggregation; if 𝐾 is even, the features would remain unchanged. In such cases with pure graph structures, the view consistently demonstrates a larger ACD and a smaller unsupervised metric, while the homophily ratio would tend toward zero as 𝜆 𝑣 2 approaches -1. On the contrary, when 𝜆 𝑣 2 nears 0, the graph structure becomes uninformative, resulting in the view with a smaller ACD and a larger unsupervised metric. In summary, we draw two conclusions: 1. ACD is more universally applicable than the traditional homophily ratio in assessing the relevance between graph structures and downstream tasks. 2. The dominant view, mined through our unsupervised method, essentially corresponds to the view with the maximum ACD value, which ensures the effectiveness of unsupervised dominant view mining. 
experiments 6.1 datasets and metrics: 
 Datasets. We employ five publicly available real-world benchmark datasets and a large-scale dataset. ACM [5] , ACM2 [7] , and DBLP [41] are citation networks. Yelp [18] and Amazon [9] are review networks. MAG [33] is a large-scale citation network, constituting the largest dataset in multi-relation graph clustering thus far.Metrics. We adopt four popular clustering metrics, including Accuracy (ACC), Normalized Mutual Information (NMI), F1 score, and Adjusted Rand Index (ARI). A higher value of them indicates a better performance. Baselines. We compare BMGC with various baselines, including the supervised multiview graph method HAN [35] , single-view graph clustering methods VGAE [12] and DGI [32] , and multiview graph clustering methods O2MAC [5] , DMGI [25] , MvAGC [13] , HDMI [11] , MCGC [22] , MGDCR [20] , DuaLGR [14] , DMG [21] ,and BTGF [28] . All other methods are unsupervised excluding HAN, which serves as the supervised baseline.Parameter Setting. Our model is trained for 400 epochs using the Adam optimizer with a learning rate of 1e-2. The weight decay of the optimizer is set to 1e-4. The recalculation interval 𝑡 for the dominant view is every 50 epochs. We set the representation dimension 𝑑 𝑟 to 64 for ACM2 dataset and 10 for the other datasets. The temperature parameter 𝜏 is fixed at 1. The radius of graph propagation, 𝐾, is fixed at 3 and the teleport probability 𝛼 is tuned in [0, 0.3, 0.5]. All experiments are implemented on the PyTorch platform using an Intel(R) Xeon(R) Platinum 8352V CPU and a GeForce RTX 4090 24G GPU.To evaluate the performance of our model, we compare BMGC with multiple baselines on five real-world datasets. For the supervised baseline HAN, we employ k-means on the node embeddings of the test set to yield clustering results. We conduct single-view clustering methods separately for each view and present the best results. Generally, BMGC consistently outperforms all compared methods regarding four metrics over all datasets. From Table 1 , we have the following observations:• The advantages of BMGC become evident when compared to other methods. In particular, our model significantly outperforms existing methods, including the supervised baseline, on Amazon and ACM2 datasets. Regarding second-place results on Amazon, our model improves NMI and ARI by 42.9% and 32.7%, respectively. • In general, multiview graph methods outperform single-view methods like VGAE and DGI, demonstrating the superiority of multiview methods in graph clustering. However, in the Yelp dataset, most multiview baselines underperform compared to single-view methods, which may be attributed to the fact that these multiview methods overlook the imbalance among different views, leading to worse performance. Moreover, while the supervised baseline HAN surpasses the unsupervised baselines on most datasets, BMGC still outperforms it, underscoring the superiority of our method. • Our model outperforms O2MAC which considers information differences among views. O2MAC retains only the most informative view while discarding others, which to some extent degenerates into a single-view method with worse results. Our model uses all the views and achieves better results by aligning the other views with the dominant view.To further compare BMGC with other methods in addressing the imbalanced problem, we introduce a new synthetic dataset based on cSBM [4] , named multi-relational cSBM. The multi-relational cSBM initially generates three views, each possessing unique graph structures with uniform homophily ratios, and sharing a common feature To reveal the performance discrepancies of different views, we use SGC on each view to obtain view-specific aggregated features and then obtain clustering results through k-means. We select several representation learning-based approaches for comparison. The results, as shown in Table 2 , indicate that a higher perturbation ratio leads to poorer performance for all methods. Our detailed observations are as follows.First, the majority of multiview graph clustering methods yield unsatisfactory results. As the perturbation ratio increases, their performance degrades to a lower level. Second, as the perturbation ratio reaches 150%, the performance of the comparative methods even drops below the SGC result in view 1, indicating that when there is extensive noise in certain views of the dataset, the performance of multiview methods may deteriorate compared to the single view methods. In our method, aligning with the dominant view prevents the result from being impaired by low-quality views with noise. Third, our model maintains relatively stable performance as the perturbation ratio increases, with a maximal variation range of 17.7%, 11%, and 2.6% for NMI, ARI, and ACC respectively, showcasing the robustness for noisy data.To evaluate the efficiency of BMGC, we conduct experiments on a large-scale multi-relational graph MAG. We select some scalable representation learning-based methods as baselines, while the remaining models run out of memory. We set the representation In summary, across all datasets, BMGC consistently exhibits superior performance. The stable results obtained in these experiments demonstrate the effectiveness of our methods in addressing the view imbalance of multi-relational graphs.To validate the effectiveness of different components in our model, we compare the performance of BMGC with its three variants:• Employing BMGC without L 𝐴𝐷𝑉 to show the significance of alignment with the dominant view. • Employing BMGC without L 𝐴𝑁 𝐹 to observe the impact of alignment with the node features. • Employing BMGC without L 𝐶𝐿𝑈 to reveal the influence of the dominant assignment on clustering performance.Based on Table 4 , we can draw the following conclusions. First, the results of BMGC are better than all variants, indicating that all components are critical to our model. Second, the loss of alignment with the dominant view (L 𝐴𝐷𝑉 ) seems to make the most contribution to the results, while the loss for alignment with the node features (L 𝐴𝑁 𝐹 ) contributes more to Amazon. This could be attributed to the universally subpar quality of all graph structures within the Amazon dataset, thereby amplifying the importance of node features. Additionally, the dominant assignment (L 𝐶𝐿𝑈 ) indeed improves clustering performance.Effectiveness of Unsupervised Mining. We delve deep into examining the impact of the perturbation ratio on both the accuracy and the unsupervised metric (∥𝑋𝑋 ⊤ -𝑋 𝑣 (𝑋 𝑣 ) ⊤ ∥ 2 𝐹 / 𝑁 ) in View 3 of the synthetic dataset. As depicted in Fig. 3a , it is conspicuous that with the increase of the perturbation ratio from 0 to 150%, the accuracy consistently decreases, indicating a continuous decline in view quality. In parallel, the corresponding unsupervised metric indeed rises. This highlights the effectiveness of our unsupervised dominant view extraction method, aligning with the conclusions drawn in the theoretical analysis in Section 5.Reliability of Dynamic Mining. To provide a detailed description of the process through which our model uncovers the dominant view, we demonstrate the evolution of the unsupervised metric (∥𝑋𝑋 ⊤ -𝑍 𝑣 (𝑍 𝑣 ) ⊤ ∥ 2 𝐹 / 𝑁 ), used to mine the dominant view, for each view of the ACM dataset. As illustrated in Fig. 3b , the data points on the y-axis represent the aggregated node features used to initialize the dominant view. These points are connected by dashed lines to subsequent data points derived from node representations. Throughout the training, the metrics of both views decrease, and the PAP view consistently exhibits lower values compared to the PSP view. This consistent trend indicates that PAP emerges as the dominant view, aligning seamlessly with our empirical analysis. After 250 epochs, the metrics converge. This result emphasizes the reliability of dynamically excavating the dominant view.We conduct a hyper-parameter analysis on the teleport probability 𝛼 and the radius of graph propagation 𝐾 on three datasets ACM, Yelp, and Amazon. The result is given in Fig. 4 . From the figure on the left, we can observe that our model shows low sensitivity to the change of 𝛼. However, when 𝛼 is too low, the performance shows a noticeable decrease. This can be attributed to the fact that the lower value of 𝛼 leads to a decreased influence of the features of the original nodes in the propagation process. In the figure on the right, we can see that the performance is stable to the change of 𝐾. Notable performance can be achieved when 𝐾 is small, improving the efficiency of the model in practical applications. 
conclusion: 
 In this study, we thoroughly investigate the prevalent challenge of view imbalance in real-world multi-relational graphs. We introduce a novel metric, the Aggregation Class Distance, to empirically quantify structural disparities among different graphs. To tackle view imbalance, we propose Balanced Multi-Relational Graph Clustering, which dynamically mines the dominant view throughout the training process, collaborating with representation learning to enhance clustering performance. Theoretical analysis validates the efficacy of unsupervised dominant view mining. Extensive experiments and in-depth analysis on both real-world and synthetic datasets consistently demonstrate the superiority of our model over existing state-of-the-art methods. 
 
 Appendix:  


Decision: This paper received a mixed rating from reviewers. From their reviewers, although this paper has some merits, most of the reviewers are not convinced with the major concerns including experimental analysis and novelty. I have also checked the concerns raised by the reviewers carefully, especially Reviewers 4T42 and yDzV. Overall, the paper stands below the borderline. I'm inclined to reject the paper and encourage the authors to revise the paper for future venues.

***TPC Addendum*** 
The paper has received a split verdict and is at the borderline of acceptance. Given two very strong positive votes and some improvement in scores after rebuttal, the TPC are suggesting an acceptance to allow for the debate and the conversation to continue at the conference.

Reviews: review: paper_summary: paper_summary: The paper addresses the issue of view imbalance in multi-relational graphs and proposes a new method to enhance clustering performance. The BMGC framework introduces the Aggregation Class Distance (ACD) metric to quantify structural disparities among different graph views. It employs unsupervised dominant view mining and dual signals guided representation learning to dynamically identify the dominant view and improve clustering results. Extensive experiments on real-world and synthetic datasets demonstrate the effectiveness of BMGC, claiming it outperforms existing methods.
strength_weakness: strength_weakness: - The unsupervised method for identifying the dominant view dynamically throughout training is innovative and addresses a crucial challenge in multi-relational graph clustering.
- The paper provides extensive experimental results on both real-world and synthetic datasets, showcasing the robustness and superiority of BMGC over existing methods.
limitations: limitations: - How robust is the unsupervised dominant view mining method to variations in the quality of different views?
- Can the authors provide more detailed empirical validation of the ACD metric in various graph settings? How does ACD compare with existing metrics in terms of effectiveness and reliability?
- What are the impacts of different hyperparameter settings on the performance of BMGC? Are there specific guidelines for selecting these parameters?
- Can the authors provide more detailed results or case studies on the scalability of BMGC, especially with significantly larger datasets and more complex graph structures?
- Please provide the variance of the main results to demonstrate the robustness of the method.
- Please provide the code link to enhance the persuasiveness of the results.
paper_summary: paper_summary: To address the question regarding the importance of the views in a multi-relational graph, the authors proposed a new metric, Aggregation Class Distance (ACD), which is utilized to determine the most dominant view. ACD is used to empirically quantify structural disparities among different views of the multi-relational graph while considering the node features (attributes) and their corresponding structural connectivity (edges in adjacency matrix). Based on it, a novel clustering method and theoretical analysis are provided.
strength_weakness: strength_weakness: 1. The idea is interesting and novel. The proposed method is theoretically guaranteed.
2. The paper is well-organized and articulates the problem statement, methodology, and findings clearly. The introduction of new concepts like ACD and the explanation of the BMGC framework are coherent. In particular, the figures improve the paper presentation.
3.The authors have conducted experiments to show different perspectives on their proposal and provided a link to the source code.
limitations: limitations: 1. The objective function is a combination of three terms. However, there is no hyperparameters, which one is more important?
2. More descriptions about the design of ACD and the results in other evaluated datasets could be given. 
3. It would be better is the clustering results from different methods are visualized.
paper_summary: paper_summary: This paper finds the imbalance issue of multi-relational graphs and defines a new metric to measure it. To solve this problem, the authors propose a novel clustering method BMGC, which consists of unsupervised dominant view mining and dual signals guided representation learning. Theoretical and experimental analysis verify its effectiveness. Overall, the technical contributions are solid and sound.
strength_weakness: strength_weakness: 1.The found imbalance phenomenon is quite interesting, which inherently limits the performance of existing graph clustering methods. I believe this finding opens a new direction for improving graph clustering performance in the future.
2.The proposed BMGC method is novel. Theoretical analysis shows its effectiveness. The approach is significant in the Multiview clustering community.
3.Comprehensive experiments on synthetic and real graphs show the effectiveness and efficiency of the proposed method, which are convincing to me.
limitations: limitations: 1.The Algorithm is missing. It is unclear how the objective function (17) is solved. Adding and describing an algorithm for the entire workflow would strengthen this paper.
2.The writing could be improved and carefully checked. For example, “Most of them start by unsupervised learning of node representations and -> Most of them start with unsupervised learning of node representations and”,” Recent theoretical advancements have demonstrated the potential-> Recent theoretical advances have demonstrated the potential”.
3.Some references are missing. For example, the reconstruction cosine loss in Eq.(6) should be cited. It is derived from: Graphmae: Self-supervised masked graph autoencoder. 

I also have some questions.
1. What is the difference between the two terms in Eq.10? More explanations are desired.
2. What does the 'metric' represent on the y-axis in Figure 3?
3. Let's suppose that a multi-relational graph has three or more views; could it happen that two views have the same ACD score? Why? Could you please give more details regarding this case?
paper_summary: paper_summary: The paper addresses the issue of view imbalance in multi-relational graphs, where nodes are interconnected by multiple types of relationships. The authors introduce the Aggregation Class Distance (ACD) metric to quantify structural disparities among views. They propose the Balanced Multi-Relational Graph Clustering (BMGC) method, which dynamically identifies the dominant view during training and uses it to guide representation learning. This approach includes unsupervised dominant view mining and dual signal guided learning to enhance clustering performance. BMGC's scalable graph encoding improves computational efficiency. Extensive experiments on real-world and synthetic datasets demonstrate that BMGC consistently outperforms existing methods, confirming its effectiveness.
strength_weakness: strength_weakness: 1.	The paper introduces the Aggregation Class Distance (ACD) metric to quantify structural disparities among different views in multi-relational graphs
2.	The paper provides a theoretical foundation for the proposed methods, offering guarantees for the effectiveness of the dominant view mining.
3.	The extensive empirical evaluation on both real-world and synthetic datasets demonstrates BMGC's consistent outperformance over existing state-of-the-art methods
limitations: limitations: 4.	This paper leaks core novel contributions, as the proposed method appears to be a combination of existing techniques or easily obtainable methods..
5.	The loss function, which incorporates full-size negative samples in the contrastive learning objective, requires three iterations of similarity computation. This makes the approach time-consuming, especially given that the proposed method operates on the entire graph rather than employing batch-wise optimization.
6.	The experimental analysis section lacks essential details. For instance, in Section 6.5, the execution time experiments do not report the experimental environment for the baseline comparisons. Additionally, the standard deviations of the experimental results are not provided, which is crucial for assessing the robustness.
paper_summary: paper_summary: In this paper, authors address the issue of imbalanced data in multi-relational graphs by proposing a Balanced Multi-Relational Graph Clustering (BMGC) method. Additionally, authors introduce a novel metric to measure structural differences across various graphs. Theoretical analysis demonstrates the effectiveness of the proposed dominant view mining. Extensive experiments validate that BMGC achieves optimal performance.
strength_weakness: strength_weakness: 1, This paper attempts to provide a new metric for measuring graph balance.
2, The method's performance was evaluated on multiple datasets during the experiments.
limitations: limitations: 1, The problem of imbalance in multi-relational graphs is not clearly defined. Accuracy is influenced by multiple factors, and merely pointing to low accuracy as evidence of data imbalance is insufficient to substantiate the issue.

2, The authors use performance to evaluate the effectiveness of ACD in measuring structural differences between views, which is inadequate to prove that ACD is a valid metric for assessing graph balance. Additionally, the authors claim in lines 329-332 that ACD is a supervised method, while in lines 562-564, they use it alongside unsupervised metrics to evaluate the effectiveness of the unsupervised dominant graph. It is illogical to use a supervised metric to assess the effectiveness of an unsupervised graph.

3, In section 4.1, the authors claim their method enhances scalability. What is the relevance of this claim to the problem addressed in the paper? Furthermore, there is no experimental evidence provided to substantiate the claim of improved scalability.

4, Some references need updating, such as [27], which has been published. Additionally, the reference format is inconsistent, as seen with [2], [3], and [4].

5, The readability of the figures is poor. For instance, in Figure 1(a), the x-axis tick values are incomplete, and the epoch is not labeled. Both Figure 1(a) and Figure 1(b) lack labels for the ACD metric.

6, The readability of the paper is suboptimal. It is recommended to revision the manuscript.