Multi-attributed graphs, in which each node is characterized by multiple types of attributes, are ubiquitous in the real world. Detection and characterization of communities of nodes could have a significant impact on various applications. Although previous studies have attempted to tackle this task, it is still challenging due to dificulties in the integration of graph structures with multiple attributes and the presence of noises in the graphs. Therefore, in this study, we have focused on clusters of attribute values and strong correlations between communities and attributevalue clusters. The graph clustering methodology adopted in the proposed study involves Community detection, Attribute-value clustering, and deriving Relationships between communities and attribute-value clusters (CAR for short). Based on these concepts, the proposed multi-attributed graph clustering is modeled as CAR-clustering. To achieve CAR-clustering, a novel algorithm named CARNMF is developed based on non-negative matrix factorization (NMF) that can detect CAR in a cooperative manner. Results obtained from experiments using real-world datasets show that the CARNMF can detect communities and attributevalue clusters more accurately than existing comparable methods. Furthermore, clustering results obtained using the CARNMF indicate that CARNMF can successfully detect informative communities with meaningful semantic descriptions through correlations between communities and attribute-value clusters.
Community detection is a task to detect densely connected
subgraphs as communities. Nodes in a community tend to share same
or similar properties, such phenomenon is called homophily
effect [
Moreover, using the attributes in a graph is advantageous to
realize high-quality community detection as well as to
understand the characteristics of communities. Multi-attributed graphs
are reasonable models of real-world networks such as social
networks, co-author networks, protein-protein interaction networks,
etc. In fact, several works have proposed algorithms that employ
attribute information (i.e., shared interests or functional
behaviors of each community) to detect not only communities but also
their semantic meanings [
However, community detection and extraction of semantics
in multi-attributed graphs remain challenging due to
dificulties on integrating graph structures and multiple attributes of
diferent types. Community detection and extraction of
semantics involves multiple steps. First, useful information from each
attribute must be extracted because certain node attributes
describe diferent aspects. Second, all extracted information must
be exploited to enhance community detection by efectively
integrating heterogeneous information. Notice that the previous
works [
To overcome these dificulties, we propose a novel clustering scheme based on the following two assumptions: (1) Relevant attribute values form clusters by attribute type. This is based on the observation that an attribute reflects a node’s interests in a network. Hence, an attribute tends to be associated to a specific group of values related to an interest. For example, in a co-author network where the nodes correspond to the authors (researchers), each author typically has specific research interests (e.g., AI, data mining, and database). Thus, attributes (e.g., paper title and conference) present biased values according to interests. Consequently, it is possible to identify clusters of attributes values (attribute-value clusters) reflecting a node’s interests. (2) Communities are strongly correlated with attribute-value clusters. This is related to the previous assumption. Consider the example above. The nodes in a community share similar interests (e.g., research interests) and consequently, similar attributevalue clusters (e.g., research topics, and conferences). Conversely, if some nodes (researchers) have similar attribute values, they should share similar interests and can be grouped in the same community.
Exploiting the correlation between communities and multiple attributes should improve the quality of community detection as well as attribute-value clustering. Using the information from diferent sources (attributes) to alleviate the efect of noise (e.g., missing values and errors), we simultaneously implement community detection and attribute-value clustering.
Based on the aforementioned ideas, we study a novel clustering scheme for multi-attributed graphs, called CAR-clustering. CAR includes Community detection, Attribute-value clustering, and deriving Relationships between communities and attribute-value clusters for multi-attributed graphs. Additionally, we develop a novel clustering algorithm called CARNMF, which employs a non-negative matrix factorization (NMF).
The contributions of this paper are summarized as follows: graph, how can community detection and attribute-value clustering be performed for diferent types of attributes in a cooperative manner? (ii) How should reasonable relationships be determined between communities and attributevalue clusters for each type of attribute? • We develop a novel algorithm CARNMF, which achieves CAR-clustering. Specifically, a dedicated loss function is designed to perform multiple NMFs simultaneously. • We conduct experiments using real-world datasets (DBLP computer science bibliography and arXiv physics bibliography). The accuracy of CARNMF with respect to community detection and attribute-value clustering and a comparison to other methods are examined. Relative to comparative methods, CARNMF achieves a better accuracy of up to 11% for community detection and up to 22% for attributevalue clustering. Furthermore, CARNMF detects informative communities and their rich semantic descriptions by correlating multiple types of attribute-value clusters. 2
Community detection in graphs is a current topic of interest in
graph analysis and AI research. Existing works for non-attributed
graphs can be categorized according to the techniques used:
graph separation [
Recently, several works have addressed the problem of
detecting communities and their semantic descriptions on
nodeattributed graphs. [
The aforementioned works only consider single textual attributes or uniformly handle multiple attributes without any distinction. In reality, each attribute represents diferent aspects of the nodes. In our research, we deal with heterogeneous attributes individually. In addition to community detection, we perform clustering over attribute values for each attribute, which, in turn, can be used to improve the quality of communities detected.
Some works have investigated clustering over networks
containing diferent types of nodes and/or edges. [
In this work, we deal with multi-attributed graphs, where each node is characterized by two or more attributes. Given such a graph, CAR-clustering is used to solve the following three subproblems: community detection, attribute-value clustering, and derivation of relationships between communities and attributevalue clusters, which have been independently studied. Below, we provide the formal definitions which are necessary to define the clustering scheme. 3.1
Multi-attributed graph G is defined by extending weighted graph G′ with several attributed graphs Gt for attribute t ∈ T. The following are formal definitions.
Definition 1 (Weighted graph). Weighted graph G′ is deifned by a triplet, ⟨V, E, W⟩, where V is a set of nodes, E(⊆ V × V) is a set of edges, and W : E → R+ is a map of edge weights. □
Definition 2 (Attributed garaph). Attributed graph Gt = ⟨V ∪ Xt , Et , Wt ⟩ of attribute t ∈ T is a bipartite graph consisting of set V of nodes, set Xt of attribute-values, a set of edges Et ⊆ V × Xt , and Wt : Et → R+ is a map of edge weights. □
Definition 3 (Multi-attributed graph). Given weighted graph G′ = ⟨V, E, W⟩ and a set of attributed graphs {Gt }t ∈T where Gt = ⟨V ∪ Xt , Et , Wt ⟩, multi-attributed graph G = ⟨G′, {Gt }t ∈T⟩ is a union of these graphs. □ 3.2
Given a multi-attributed graph, information can be extracted from diferent perspectives. In this work, we extract communities, attribute-value clusters, and the relationship between them.
Community. For a multi-attributed graph, a set of nodes with the following properties is regarded as a community. (1) Nodes in a community are densely connected with each other and sparsely connected with other nodes. (2) Nodes in a community tend to share common values in distinct attributes. This study assumes that communities can overlap. That is, each node belongs to more than one community. This assumption is reasonable for real applications. Formally, given the number of communities ℓ, node n ∈ V belonging to community c ∈ C is described by probability distribution p(n | c), where |C| = ℓ.
Attribute-value cluster. For attribute t ∈ T in a multi-attributed graph, similar or highly correlated attribute values can be grouped into attribute-value clusters. Herein, we assume overlapping clusters. That is, each attribute-value belongs to more than one cluster. Formally, given the number of clusters kt of attribute t ∈ T, cluster member x ∈ Xt for attribute-value cluster st ∈ St is described by probability distribution p(x | st ), where |St | = kt .
Relationship between a community and an attributevalue cluster. Nodes in a community often share common attributevalue clusters. Detecting such relationship is useful in many applications. Given community c ∈ C and attribute-value cluster st ∈ St of attribute t ∈ T, the probability that c is related to st is described as the relationship between c and st . In this work, a community may be related to more than one attribute-value cluster. Formally, this is described by probability distribution p(st | c).
CAR-clustering. CAR-clustering is formally defined by Definition 4.
Definition 4 (CAR-clustering). Given a multi-attributed graph G, CAR-clustering is to perform community detection, attributevalue clustering, and detection of the relationship between the communities and the attribute-value clusters simultaneously.□
Solving these sub-problems simultaneously is more beneficial than evaluating each one independently because, in many cases, communities and attribute-value clusters are mutually correlated. Solving the problems simultaneously exploits this correlation, leading to improved results. 4
In this section, we propose an NMF (non-negative matrix factorization)based algorithm, called CARNMF, for CAR-clustering. CARNMF models communities and attribute-value clusters. Additionally, we introduce an auxiliary matrix to maintain the relationship between the communities and the attribute-value clusters. A unified loss function is used to solve the diferent NMFs in a unified manner. It is assumed that the user gives the number ℓ of communities and the number kt of clusters for each attribute t ∈ T. 4.1
We represent a multi-attributed graph by two sorts of matrices: an adjacency matrix A ∈ R|V|×|V| and attribute matrices X (t ) ∈ R|V|×|Xt | for t ∈ T. An element Au,v of A corresponds to an edge eu,v = (u, v) ∈ E. Au,v = W(eu,v )/Íei, j ∈E W(ei, j ), indicating the joint probability for the presence of edge eu,v . Similarly, for t ∈ T, an element Xu(t,)x in X (t ) corresponds to an edge eu(,)x ∈ Et . Xu(t,)x = Wt (eu(,)x )/Ív,y ∈Et Wt (ev(,)y ), indicating t t t the joint probability of the presence of edge eu(t,)x . 4.2
We achieve CAR-clustering in terms of several NMFs, which correspond to the aforementioned sub-problems. To achieve CARclustering, we introduce loss functions for the sub-problems followed by a unified loss function.
Loss function for community detection. In CARNMF, communities C are denoted by a matrix U ∗ ∈ R|V|×ℓ , where each row and column correspond to a node u ∈ V and a community c ∈ C, respectively. A cell Uu∗,c represents probability p(u | c). In probability p(u, v | c), u and v are connected through community c, and is represented by Uu∗,cUv∗,c . Moreover, joint probability p(u, v), or the existence of edge eu,v ∈ E, is expressed as Íc ∈C Uu∗,cUv∗,c . Therefore, when U ∗ minimizes the following loss function, U ∗ is the best approximation of the edges in the graph.
arg min A − U ∗(U ∗)T 2 U ∗ ≥0 F
s .t . ∀1 ≤ c ≤ ℓ, U·∗,c 1 = 1 where ∥·∥F2 and ∥·∥1 represents the Frobenius norm and the ℓ1 norm, respectively.
Loss function for attribute-value clustering. In CARNMF, attribute-value clusters St of attribute t ∈ T are represented as (1) a matrix V (t ) ∈ R|Xt |×kt , where each row and column correspond to an attribute x ∈ Xt and an attribute cluster st ∈ St , t respectively. A cell Vx(,s)t represents probability p(x | st ).
To derive V (t ) from X (t ), we introduce a matrix U (t ) ∈ R|V|×kt , which denotes the relationships between the nodes and attributevalue clusters with probability p(u | st ). Using both matrices U (t ) and V (t ), probability p(u, x | st ), which is the existence t of edge eu(,)x ∈ Et in terms of attribute-value cluster st , is calculated as Uu(t,s)t Vx(,s)t . Moreover, probability p(u, x ) is derived t as Íst ∈St Uu(t,s)t Vx(t,s)t . Therefore, when U (t ), V (t ) minimize loss function, U (t ), V (t ) represent the best approximation of the edges in the graph. (2) (3) arg min U (t),V (t) ≥0
X (t ) − U (t )(V (t ))T 2
F s .t . ∀1 ≤ r ≤ kt , V·(,tr) 1 = 1
Loss function for relationship detection. In CARNMF, the relationships between communities and attribute-value clusters of attribute t ∈ T are represented as a matrix R(t ) ∈ Rℓ×kt , where each row and column corresponds to a community c ∈ C and an attribute-value cluster st ∈ St , respectively. The cell contains the probability p(st | c). We assume R(t ) is a linear transformation that maps U ∗ into U (t ), where U ∗ and U (t ) derived by Equation 1 and Equation 2, respectively. Therefore, when R(t ) minimizes the loss function, R(t ) represents the relationships between the communities and the attribute-value clusters.
arg min U (t),U ∗,R(t) ≥0
U (t ) − U ∗R(t ) 2
F s .t . ∀1 ≤ p ≤ ℓ, U·∗,p 1 = 1, Rp(t,)· 1 = 1 Equation 3 can be regarded as an NMF that decomposes the matrix of the node-by-attribute value cluster into node-by-community and community-by-attribute value cluster matrices. In other words, Equation. 3 indicates the efect of the relationship between nodes and attribute-value clusters against communities.
Unified loss function. To achieve CAR-clustering, the aforementioned three sub-problems must be solved. In this work, we attempt to solve them simultaneously by introducing a unified loss function, which is expressed as
L =
arg min U ∗, {U (t), V (t), R(t)}t ∈T
A − U ∗(U ∗)T 2
F t ∈T s .t . ∀1 ≤ r ≤ kt , ∀1 ≤ p ≤ ℓ, ∀t ∈ T, ∥U·∗,p ∥1 = 1, ∥V·(,tr) ∥1 = 1, ∥Rp(,)· ∥1 = 1
t + Õ
X (t ) − U (t )(V (t ))T 2 + λt U (t ) − U ∗R(t ) 2
F F (4) where λt for attribute t ∈ T is a user-defined parameter to control the efect of attribute-value clusters for community detection. Higher λt yields a stronger efect of the attribute-value clusters in community detection. 4.3
Similar to the ordinary NMF, the loss function in Equation 4 is
not simultaneously convex for all variables. Hence, we consider
the NMF to be a Frobenius norm optimization, where update
equations are derived based on [
Considering the Karush-Kuhn-Tucker (KKT) first-order conditions applied to our problem, we derive:
U ∗ ≥ 0, U (t ) ≥ 0, V (t ) ≥ 0, R(t ) ≥ 0 ∇U ∗ L ≥ 0, ∇U (t) L ≥ 0, ∇V (t) L ≥ 0, ∇R(t) L ≥ 0
U ∗ ⊙ ∇U ∗ L = 0, U (t ) ⊙ ∇U (t) L = 0,
V (t ) ⊙ ∇V (t) L = 0, R(t ) ⊙ ∇R(t) L = 0 where ⊙ is the element-wise product. From the Karush-KuhnTucker (KKT) conditions, we derive derivatives corresponding to the variables:
t ∈T ∇U ∗ L = − 2AT RU ∗ + 2U ∗(U ∗)T U ∗
+ Õ λt (−U (t )(R(t ))T + U ∗R(t )(R(t ))T ) ∇U (t) L = − X (t )V (t ) + U (t )(V (t ))T V (t )
+ λt (U (t ) − U ∗R(t )) ∇V (t) L = − (X (t ))T U (t ) + (V (t ))T (U (t ))T U (t )
∇Ri L = − (U ∗)T U (t ) + (U ∗)T U ∗R(t )
By substituting the corresponding gradients in Equation 4, we derive the following update rules:
AT U ∗ + Ít ∈T λt U (t )(R(t ))T U ∗ ← U ∗ ⊙ 2U ∗(U ∗)T U ∗ + Ít ∈T U ∗R(t )(R(t ))T
X (t )V (t ) + λt U ∗R(t ) U (t ) ← U (t ) ⊙ U (t )(V (t ))T V (t ) + λt U (t ) V (t ) ← V (t ) ⊙ R(t ) ← R(t ) ⊙
(X (t ))T U (t ) (V (t ))T (U (t ))T U (t ) (U ∗)T U (t ) (U ∗)T U ∗R(t )
The aforementioned update rules monotonically decrease Equation 4. However, these variables may violate the probability definition (i.e., their sum does not equal one). To satisfy constraints, ∥U·∗,p ∥1 = 1, ∥V·(,tr) ∥1 = 1 and ∥Rp(,)· ∥1 = 1, the variables are t normalized immediately after updating. The normalization is expressed as
U ∗ ← U ∗(Q∗)−1 V (t ) ← V (t )(Q(t ))−1 (16) (17)
U (t ) ← U (t )Q(t ) R(t ) ← R(t )(Q R )−1 where Q∗ = Diaдonalize(U ∗), Q(t ) = Diaдonize(V (t )), and Q R(t) = Diaдinalize(R(t )). a Diaдonalize(Z ∈ Ra×b ) = Diaд Õ
Zi,1 · · · , i=1 a Õ i=1
Zi,b ! Diaд(·) provides a diagonal matrix where the diagonals are the input sequence.
Algorithm 1 shows the optimization algorithm based on the aforementioned update rules. Matrix normalization is applied after the updates. Without normalization, each matrix may have significantly diferent values, leading to inconsistent results. Algorithm 1 describes the order of update rules and normalizations. 16: end while
Here, we analyze the computational complexity of the proposed algorithm. The equations in our algorithm have the following complexities: • Updating U ∗ (Eqs. 12 and 16) needs O(|E|ℓ + |V|ℓ2 Ít kt ). • Updating U (t ) (Eqs. 13 and 18) and V (t ) (Eqs. 14 and 18) needs O (|V| + |Xt |)kt2 + |Et |kt .
• Updating R(t ) (Eqs. 15 and 19) needs O |V|(ℓkt + ℓ2) .
In summary, the time complexity of our algorithm is follows, where iter is the number of outer iterations (lines 3–16 in our algorithm).
O iter Õ t |V|(ℓ2kt + kt2) + |Xt |kt2 + |E|ℓ + |Et |kt ! (21)
To demonstrate the applicability and efectiveness of CARNMF, we conducted a set of experiments using real-world datasets. Specifically, the performance of the proposed scheme was compared to simple baseline and state-of-the-art methods.
The experiments were performed on a PC with an Intel Core i7 (3.3 GHz) CPU with 16 GB RAM running Ubuntu14.04. CARNMF was implemented by Python 2.7.6 with Numpy 1.9.0.
We used two datasets: DBLP and arXiv.
• DBLP: Digital Bibliography Project1 is a bibliographic
database in the computer science area. DBLP contains
publication information, such as authors and conferences. We
used a part of the dataset by extracting conferences
similar to [
Each rectangle shows the top contributing nodes in the community/cluster, and the edge weights show the strength of the relationship between the community and the corresponding cluster. We chose famous researchers in diferent research domains (i.e., Jiawei Han, Michael Stonebraker, and Michael I. Jordan).
Figure 1(a) show the community and the correlated attributevalue clusters of Jiawei Han, who is a leading researcher in data mining and database areas. The results show that (1) he collaborates with Chinese researchers, (2) he publishes many papers related to data mining and database conferences (i.e., KDD, ICDM, SDM, PAKDD, and VLDB), and (3) his researches are highly correlated with topics in data mining, such as clustering and classification on large graph.
Similarly, Figure 1(b) shows the result for Michael Stonebraker, a renowned database researcher. His community is strongly related to conferences in databases (SIGMOD, VLDB, PODS, EDBT, and ICDT ). Topics such as view management, distance metric, and query evaluation are detected. Figure 1(c) shows the result for Michael I. Jordan, an expert in machine learning research. This community is strongly related to the conferences of machine learning, (NIPS, ICML, UAI, COLT, and ECML) and the topics like learn network, expert model, and prediction.
The detected communities and the associated attribute-value clusters seem to be reasonable. 5.3
The proposed scheme is compared to a baseline method as well
as state-of-the-art methods to quantitatively evaluate the
performance of community detection and attribute-value clustering.
The comparison methods include:
• NMF [
Note that, LCTA and SCI deal with a single concatenated feature of multiple attributes. Therefore, we prepare concatenated feature consisting of term, document and conference/journal, and apply these approaches on the feature.
To evaluate the qualities of these methods, we compared the
accuracy [
Definition 5 (Accuracy). Given a set S of elements, for each element n ∈ S, the true label and the cluster label generated by a method are denoted by sn and rn , respectively. Then, the accuracy 3Because NMF assumes the co-occurrences of binary relationships, paperconference (one-to-one relationship) is excluded.
(a) Communities of “jiawei han.” (b) Communities of “michael Stonebraker.”
(c) Communities of “michael i. jordan.”
Accuracy = Ín ∈S δ (sn , map(rn ))
|S|
where | · | is the cardinality of a set; δ (x, y) is a delta function
which returns 1 if x = y, otherwise 0; and map(rn ) is a mapping
function that maps rn to the equivalent label in the dataset. The
best mapping can be found by Kuhn-Munkres algorithm [
Table 4 summarizes the evaluation results. The number of communities and the number of attribute-value clusters for each attribute are each four. Each cell shows the mean and the standard deviation of the accuracies for 20 trials. N/A denotes that the method does not support the category. Values in bold indicate a significant improvement using the Student-t test, where p < 0.05.
CARNMF achieved the best performance for community detection (author) and attribute-value clustering (paper and conference/journal) with significant gaps for DBLP dataset (respectively 11%, 22% and 7%) and for arXiv dataset (respectively 3%, 4% and 2%) relative to the comparative methods. In particular, CARNMF has an improved clustering quality compared to NMF by taking the relationships between communities and attribute-value clusters into account.
Table 5 summarizes evaluation of efects from taking multiple attributes into account. The table showcases results where diferent combinations of attributes are used, e.g., “(T-C)” means term and conference attributes were used. This result shows that the proposed method works the best when taking as many attributes as possible. As expected, the basic tendency is that as the number of attributes increases, the accuracy increases.
Table 3 lists the detected topics from DBLP using CARNMF when the number of topics is set to four. Our method successfully detects the four major research topics. Specifically, Topic 1 containing retriev, inform, search, queri and web seems to correspond to information retrieval, and Topic 2 containing mine, pattern, cluster, graph and frequent correspond to data mining. Topic3 contains words “ learn, network, kernel, bayesian, reinforc”, which are typical words of machine learning. Topic4 is a topic of database containing words “ query, databas, optim, xml, manag”, which are popular topics on database researches.
This section discusses the efect of parameter λt for each attribute. The larger the λt value, the greater the influence of the attributevalue cluster for t ∈ T is on the community. Therefore, optimal parameter setting should result in better results. Figures 2 shows the behavior of the accuracy with diferent values with respect to diferent attributes. For each evaluation, λs (s , t ) of the other attributes were fixed. In most cases, the accuracy shows a convex form and the peak is around 10−2. More importantly, the accuracy is insensitive to the setting, making tuning easier.
In this section, we experimentally provide convergence analysis to optimize the proposed loss function in Equation 4. Figures 3(a) and (b) show the convergence curve of the loss function for DBLP and arXiv, respectively. In addition, the accuracy of each iteration is plotted. The black line shows the value of the loss function. The red, green, and blue lines show the accuracy of community detection and attribute-value clustering for author, paper, and conference/journal, respectively. As the number of iterations increases, the loss function decreases while the accuracy improves.
This section analyzes computational eficiency in terms of the numbers of communities and attribute clusters. When the numbers are fixed to four as experiments above, the running times of CARNMF on the DBLP (arXiv) dataset are 1.186 ± 0.253s (0.682 ± 0.138s). When changing the numbers of communities and term clusters to 50, while those of paper and conference remain four, the running times increases to 7.471 ± 0.563s (DBLP) and 6.526 ± 0.172s (arXiv). These values are still reasonable for various applications.
Moreover, we examine the running time of our method by changing the number of nodes in an input graph. Theoretically, as discussed in Section 4.4, the computational complexity is dependent on the number of vertices, that of edges, and that of distinct values of each attribute. As most of real-world graphs are modeled as scale-free networks, edges in a graph are very sparse, therefore, we examine the sensitivity of processing time on the proposed method in terms of the number of nodes. In this experiment, we selected all of the papers on DBLP, and construct the multi-attributed graph as same manner as described in Section 5.1. We set the number of communities and clusters are four. 100 80
) 60 ( % y c ra 40 cu c
A (b) arXiv
10 00 10000 20000 30000 40000 50000 60000 70000 80000 90000
# of nodes Figure 4 shows that the time complexity of our method is almost linear to the number of nodes. From the figure, we ensure that the time complexity of our method is linear to the numbers of nodes and edges (as shown on Equation21). Therefore, when the input graph is sparse, our method is highly eficient. 6
In this paper we have proposed CAR-clustering, which includes
community detection, attribute-value clustering, and extraction
of their relationships, for clustering over multi-attributed graphs.
We have also proposed a novel algorithm CARNMF based on NMF.
CARNMF employs a unified loss function to simultaneously solve
diferent NMFs. This approach is better than the state-of-the-art
methods in that it can exploit the correlation between
communities and attribute-value clusters for enhancing the quality of the
result. Our experiments have demonstrated that CARNMF
successfully achieves CAR-clustering. CARNMF has detected
reasonable communities with meaningful semantic descriptions via the
relationship between communities and attribute-value clusters
for real-world datasets. These results are useful for many
applications such as node property estimations [
This research was partly supported by Japan Agency for Medical Research and Development (AMED).