A Relaxed Symmetric Non-negative Matrix Factorization Approach for Community Discovery (Extended Abstract)

1 Introduction

Complex networks are pervasive across a multitude of real scenarios, e.g., social relationships in social platforms [Liu et al., 2020] and protein interactions in bioinformatics [Manipur et al., 2023]. Community stands as a fundamental attribute of a network, serving as a window into its underlying organizational architecture, making community discovery shed lights on some practical applications such as predicting epidemic transmission trends and identifying biological modules [Gisdon et al., 2024]. Traditional methods such as graph segmentation [Wang et al., 2021], spectrum analysis [Huang et al., 2020], and intelligent optimization [Yang et al., 2024] operate on straightforward principles but often yield suboptimal accuracy. Learning-based methods treat community discovery as a representation learning task. They offer the merits of flexible modeling and high accuracy, becoming a favored choice in current research. Among them, non-negative matrix factorization (NMF) exhibits notable suitability for graph clustering owing to two distinct merits [He et al., 2022]: 1) it possesses inherent clustering capabilities-previous work [Ding et al., 2005] has demonstrated that NMF is equivalent to advanced clustering techniques such as k-means; and 2) it offers excellent interpretability for cluster structures, owing to their linear expression abilities.

This paper is an extended abstract of a paper [Liu et al., 2024b] that won the Best Paper Award at PRICAI 2024.

Existing NMF-based community discovery methods aim to enhance their representation learning capabilities. [Sun et al., 2017] introduces an approach based on non-negative encoder-decoder architecture for community discovery; [Leng et al., 2019] proposes a graph-regularized NMF model with Lp-smoothness constraints; and [Berahmand et al., 2023] presents a new augment graph regularization NMF model for attributed networks. However, these methods do not fully exploit the inherent symmetry property of undirected networks. In contrast, a symmetric non-negative matrix factorization (SNMF) model learns a single feature matrix X for an undirected network and approximates its adjacency matrix A, i.e., Â=XX T . Notably, [Ding et al., 2005] establishes the equivalence between SNMF and spectral clustering, ensuring wellinterpretable clustering properties. Building upon the flexible SNMF, an array of SNMF-based community discovery methods has emerged [Yang et al., 2015; Ye et al., 2020; Luo et al., 2022; Lv et al., 2023; Guan et al., 2024].

Enhancing the representation learning capacity of SNMF presents a significant challenge. [Kuang et al., 2015] introduces a symmetric NMF model that adopts a constraint term to reduce the discrepancy between two feature matrices. [Li et al., 2023; Liu et al., 2024a] extend this work by transforming a standard SNMF model into a penalized non-symmetric NMF model. Such an approach enforces the equality of feature matrices to capture the inherent structural symmetry by introducing an equality-regularization term into the learning objective. However, a critical challenge remains: balancing representation learning capacity and symmetry. With a small coefficient, the model may inadequately represent symmetry, while with a large coefficient it overly emphasizes the regularization term, compromising the fitting of overall loss and representation learning.

To strike a balance between symmetry representation and learning capacity, this paper proposes RSN-a novel relaxed symmetric non-negative matrix factorization model for community discovery, with four-fold ideas: 1) Leveraging multiple feature matrices to represent a network, thus preserving its representation learning capacity; 2) Introducing symmetry constraints to enable the model to fully recognize the inherent symmetry; 3) Incorporating graph regularization that captures the local topological characteristics to maintain the network's intrinsic geometry; and 4) Adopting the ADMM principle to solve RSN efficiently, thus facilitating the independent learning of decision parameters.

Main contributions of this work are summarized as follows: 1) An accurate community discovery model, i.e., RSN. It leverages the well-designed symmetry constraints to enlarge the latent feature space for ensuring its representational capacity, and adopts graph regularization to preserve a target network's intrinsic geometry, thereby guaranteeing RSN's high representation learning ability. 2) An efficient learning scheme. An ADMM-based learning scheme efficiently solves RSN, addressing the symmetry and non-negativity constraints. Empirical evaluations conducted on six authentic and openly accessible networks demonstrate that the RSN-based community discovery model substantially outperforms existing baseline and SOTA methods in terms of detection accuracy.

The paper is organized as follows: Section 2 gives the foundational concepts and problem formulation. Section 3 presents the RSN-based model for community discovery. Section 4 elucidates the experimental results. Finally, Section 5 concludes this study.

2 Preliminaries

2.1 Problem Statement

Given a network G=(V, E), where V={v1, v2, …, vn} is a set of n nodes and E={eij | i, j∈{1, 2, …, n}} is a set of m edges, its topology is described by an adjacency matrix A=[aij]∈ℝ n×n which is a symmetric and binary matrix for an undirected and unweighted network concerned in this work. Its entry aij is assigned to one if eij∈E and zero otherwise. Given G with K communities, a community discovery model aims to identify the community set C={Ck | Ck, ∪k=1 K =V, CkCt, 1kK, 1tK}, where Ck is the k-th community in C, and ∪ denotes the union set [Liu et al., 2023].

2.2 NMF-based Community Discovery

An NMF-based community discovery model assumes that the approximation of each entry aij, i.e., âij, is affected by K communities in a network. Hence, we suppose a non-negative latent factor for community assignment X∈ℝ n×K and the one for the basis U∈ℝ n×K . NMF learns an approximation  to A with U and X, yielding Â=UX T . Thus, a non-convex loss function based on the Euclidean distance between A and  is given as

where ||·|| calculates the Frobenius norm.

It is worth mentioning that an NMF model does not consider the description of the network's symmetry. To preserve A's symmetry, an SNMF model leverages a single latent factor to learn its approximation [Luo et al., 2022]. Hence, the loss function is given as

An NMF-based method implements community discovery by taking X as a membership soft indicator: ∀i∈{1, 2, …, n} and k∈{1, 2, …, K}, xik can be considered as the probability that node vi belongs to community Ck, i.e., [Liu et al., 2023],

3 Methods

3.2 Optimization Objective

To capture the inherent symmetry, we introduce an equalityconstraint term, i.e., X=Y, into RSN's objective function:

where A is an adjacency matrix, decision parameters X and Y are desired feature matrices for forming the low-rank approximation  to A, i.e., XY T .

In (4), by setting a trade-off coefficient to balance the generalized loss and the constraint term, the equality-like symmetry constraint term "X=Y" enforces two feature matrices to be identical during the training process, thus capturing symmetry of the target network [Liu et al., 2024a]. However, in practical applications, achieving a balance between representational capacity and symmetry is challenging, because the solutions of the two feature matrices either become too similar thus making the model reduce to an SNMF model, or fail to capture the symmetry effectively.

To overcome this issue, we introduce two auxiliary parameters P and Q to separate the involved constraints, i.e., symmetry and non-negativity, from the decision parameters

To make the model well aware of the local topological geometry of the target data, we further introduce a graph regularization term to (5) and extend it as

where tr() denotes the trace of a matrix. λ>0 is a tunable hyperparameter that adjusts the effect of graph regularization. L=D-A is the Laplacian matrix of A, and D is the degree matrix where each entry is calculated as dii=∑lail. Note that the learning objective of RSN in (6) exhibits several merits:

• It employs asymmetric factorization to avoid the reduction of feature space through two distinct feature matrices.
• By transforming the equality-like symmetry constraints on decision parameters into auxiliary variables, it relaxes the strong assumption of equality between X and Y, which enlarges the feature space and degrees of freedom.
• The introduction of graph regularization ensures that the model preserves the intrinsic local topology, enhancing its awareness of the local community structure.

• While imposing non-negative constraints on auxiliary variables, a generalized loss is constructed based on decision parameters. Such decoupling of non-negative constraints from decision parameters facilitates the optimization of the generalized loss.
• The representation of matrix A's symmetry is guaranteed by the relation Â=PQ T .

3.2 ADMM-based Learning Rules

To resolve (6), we employ the ADMM principle to design an efficient learning scheme for RSN. Thus, we begin by formulating an augmented Lagrangian function

where ○ denotes the Hadamard product. nK , nK and nK are three Lagrangian multipliers related to the equality constraints, i.e., X-P, Y-Q and P-Q. The effects of augmentation terms, i.e., 2 2 F X P  - , 2 2 F Y Q  - and 2 2 F P Q  - , are adjusted with three coefficients, i.e., α, β and ș. The nonnegative constraints can be implemented by projecting P and Q onto the non-negative field of real numbers.

With the ADMM framework [Luo et al., 2023], let t and t+1 represent the current and updating iteration status of parameters, and we obtain the following learning sequences:

where  denotes the gradient, and Ș is the learning rate of gradient ascent. Next, we present the detailed derivation of the solutions of X, Y, P, Q, ,  and  one by one.

1) Solution of X

According to the principle of ADMM, X can be iteratively optimized by fixing the other variables. Consequently, the Lagrangian function is rendered convex for X, thus facilitating an analytical resolution, i.e.,

With (9), the solution of X can be achieved as

2) Solution of Y

By fixing the other variables, the solution of Y is achieved by optimizing it independently. Thus, we have

With (11), we achieve the solution of Y, i.e.,

3) Solution of P

Similarly, the solution of P is obtained by fixing all the other parameters to optimize itself alternatively. We have

yielding the solution of P, i.e.,

which is projected onto the non-negative range to fulfill the non-negative constraint.

4) Solution of Q

By fixing the other variables except for Q, we have

yielding the solution of Q, i.e.,

where values are also projected onto the non-negative range. 5) Solution of Lagrangian multipliers

Based on the principle of ADMM, Lagrangian multipliers, i.e., , , and , can be optimized via the dual gradient ascent algorithm. Thus, we achieve

Based on the above analysis, an RSN model is achieved. It assigns community affiliation based on (1) by taking Q as a node-community membership indicator.

4 Experiments

4.1 General Settings

We adopt six social networks from real applications as summarized in Table 1. Three evaluation metrics are used for performance evaluation [Chakraborty et al., 2017], i.e., Modularity for hyperparameter tuning, and NMI along with AC for performance assessment of all tested methods. We compare RSN with nine baseline and SOTA methods, i.e., NMF [Lee and Seung, 2000], SNMF [Wang et al., 2008], NSED [Sun et al., 2017], ANLS [Kuang et al., 2015], GNMF [Yang et al., 2015], GSNMF [Yang et al., 2015], HPNMF [Ye et al., 2020], LpNMF [Leng et al., 2019] and HALS [Li et al., 2023]. All hyperparameters are set with their optimal values.

4.2 Comparison Results

We compare RSN with baseline and SOTA methods to verify its superiority in community discovery. The graph regularization coefficient  is tuned in {10-2 , 10-1 , 10 0 , 10 1 , 10 2 , 10 3 }, and augmentation coefficients, i.e., α, β and ș, are tuned in {2-10 , 2-8 , 2-6 , 2-4 , 2-2 , 2 0 }, and the learning rate Ș is tuned in {0.001, 0.005, 0.008, 0.01, 0.02, 0.05}. Average NMI and AC values are recorded in Tables 2 and 3. We also calculate the statistical test results in each table, e.g., average Friedman ranks and p-values with a significance level of α=0.05.

Based on the comparison results, we conclude that:

1. Relaxed symmetry constraints are effective. With the help of relaxed symmetry constraints, RSN can represent the symmetry without the degradation of representational capacity. Results in Tables 2 and 3 show that RSN outperforms GNMF on five out of six networks, except that they both get full marks on the Karate network. The phenomena tell us that considering the inherent symmetry enables RSN to achieve more accuracy results. That is to say, the proposed relaxed symmetry constraints are effective.
2. RSN achieves superior accuracy in community discovery. Higher representational capacity leads to RSN's better performance on community discovery. Results in Tables 2 and 3 demonstrate that RSN outperforms its peers in most testing cases, and achieves the highest values across NMI and AC. Moreover, RSN's average Friedman rank is always the lowest among all tested methods, which indicates its significant superiority in obtaining community discovery accuracy gain. In addition, from the statistical results of the Wilcoxon signed-rank tests, we conclude that RSN obtains significantly higher community discovery accuracy than baseline and SOTA methods on most testing cases with a confidence level of 95%.

4.3 Symmetry Study

In this part, we aim to evaluate RSN's representation learning ability regarding structural symmetry. To do this, we plot the data distributions of low-rank approximations to Flickr and Karate networks in Figure1. Naturally, if RSN can learn the symmetry of a network, its approximation is symmetric and the data will concentrate along the line y=x. As shown in Figure1, RSN describes the symmetry of target networks approximatively, which certainly indicates that the proposed relaxed symmetry constraint strategy is effective.

4.4 Convergence Study

Figure 2 plots the convergence curves of RSN on DBLP, Amazon, and Flickr networks. From it, we see that the training curve of RSN converges very fast and arrives at a stationary state within ten iterations. Hence, the experimental results support the theoretical conclusion that owing to the help of the ADMM principle, the developed learning scheme can efficiently solve the proposed RSN model.

5 Conclusion

A novel RSN approach is proposed in this paper to boost an NMF-based community discovery model's representation learning ability by incorporating the well-designed relaxed symmetry constraints to capture the inherent network symmetry and enlarge the feature space. Moreover, RSN adopts graph regularization to preserve the local geometric features. An efficient learning scheme based on the ADMM principle is developed to solve the model efficiently. Experimental results on six real networks demonstrate that the RSN-based community discovery model outperforms the baseline and SOTA methods. In our future work, we plan to investigate the adaptation of hyperparameters using intelligent optimization techniques [Pu et al., 2022; Moya and Ventura, 2025].

Acknowledgments

This work was partly supported by Guangdong Basic and Applied Basic Research Foundation grant 2023A1515110689, NSFC grant W2412112, and Guangdong Province Universities and College Pearl River Scholar Funded Scheme (2019).