Galaxy Network Embedding: A Hierarchical Community Structure Preserving Approach

1 Introduction

Network embedding is a method of learning a lowdimensional representation of vertices in a complex network, under the condition of preserving different types of structural properties of the network. It enables effective applications of many general machine learning methods to network analyses, such as vertex classification, network clustering, network visualization and and social influence analysis [Bhagat et al., 2011; He et al., 2012; Song et al., 2015].

Network embedding studies include structure-preserving methods [Grover and Leskovec, 2016; Wang et al., 2017] and property-preserving methods [Hu et al., 2017]. Our paper belongs to the former. In terms of structure-preserving methods, inspired by Skip-gram in word2vec [Mikolov et al., 2013a], many methods consider the vertex context and represent a vertex with its nearby vertices [Perozzi et al., 2014; Grover and Leskovec, 2016; Tang et al., 2015]. In addition to preserving the microscopic structure, the community structure, one important mesoscopic description of network structure, is incorporated into network embedding in MNMF, of which the learned embedding space can well reflect the organizational structures and functional components of networks [Wang et al., 2017].

∗These authors contributed equally to the work.

†Corresponding Author

Essentially, these methods mainly focus on preserving neighborhood information, or community structure at a particular scale. However, the community structures in complex networks are often hierarchical [Clauset et al., 2006], and many complex networks, such as social networks, air transportation networks, and metabolic networks, exhibit explicit hierarchical structures. Such a hierarchical structure greatly enriches the community structure and connects the community structure at different scales [Sales-Pardo et al., 2007]. For instance, in a social network among college students, the hierarchical structure could include the university, the department within the university, and the enrollment year within the department, etc. Hierarchical network embedding aims at a succinct vector representation of the network that encodes the rich hierarchical structural information, which could make it much easier to analyze the network at different scales.

It is challenging to formulate the hierarchical community preserving network embedding. Not only the topological relationship between the nodes 1 in the same layer of the hierarchical tree needs to be considered, but the relationship between the nodes in different layers needs to be considered as well. In addition, efficiently implementing the embedding method is a challenge as well.

Conceptually, a hierarchical community network embedding should preserve two types of relationship information: One is the local information that represents the microscopic structure (pairwise nodes similarity) in the same community at a certain layer; the other is the hierarchical information. Horizontally, the nodes in the same community are more similar to each other. Vertically, a community in a lower level has a greater cohesion degree than a community in a higher level (e.g. in the solar system, the earth is closer to the moon, farther from the sun).

1 In this paper, we consistently use the term "vertex" to represent a node in the network, while using the term "node" to represent a node in the hierarchical tree.

In this paper, inspired by the natural hierarchical structure of a galaxy with its stars, planets, and satellites, we propose the Galaxy Network Embedding (GNE) model. In particular, several properties of the galactic hierarchical structure influence our modeling and implementation, as we now explain. As most network embedding schemes, we formulate network embedding as an optimization task, with constraints on both the local community structure and the global hierarchical structure. For preserving pairwise similarity in local communities, we extend the LINE method [Tang et al., 2015]. For global hierarchical structure constraints, we draw inspiration from the galactic hierarchy where celestial bodies belonging to the same subsystem have much shorter distance than (a) their distance to the same level celestial bodies in another subsystem, and (b) their distance to the center of a higher level system (e.g. satellites of one planet are much closer to one another than they are to satellites of a different planet, and than they are to the sun of their planet). We turn the first observation as a horizontal constraint and the second one as a vertical constraint and impose them for hierarchical network embedding. Moreover, when implementing the embedding, for the set of sibling nodes of the same parent node in the hierarchy, we embed them on a sphere with the parent at the center (Fig.1 (c)). This also resembles the galaxy structure, for example satellites of the same planet are at similar distance scale to the planet (thus on an approximate sphere centered at the planet), comparing to the distance scale between planets, and similar situation can be said for planets surrounding their sun. The spherical embedding of a subsystem in the hierarchy makes our embedding implementation efficient.

To summarize, we make the following contributions:

• We propose the Galaxy Network Embedding (GNE) model with horizontal and vertical constraints to preserve the hierarchical community structure at any scale.
• We present a novel spherical embedding method that leads to an efficient and effective implementation in the GNE model.
• We conduct extensive experiments on three real-world networks and four synthetic networks with explicit hierarchical structures, and the results demonstrate that our model can integrally preserve the hierarchical community structure and is significantly superior to other models on vertex classification and network visualization.

2 RelatedWork

Network Embedding. Network embedding maps the vertices or edges of a network into a low-dimensional vector space, which is beneficial to vertex classification and network visualization. It is well recognized that network representation has two goals: reconstructing the original network and supporting network inference. Manifold learning aims to reconstruct all the links, causing overfitting and limiting the network inference ability seriously [Tenenbaum et al., 2000]. In order to support network inference, structurepreserving method and property-preserving method are proposed. In terms of structure-preserving methods, inspired by the word2vec in NLP [Mikolov et al., 2013a], some methods consider the vertex context and represent a vertex with its nearby vertices [Perozzi et al., 2014; Grover and Leskovec, 2016; Tang et al., 2015]. In addition to preserving the microscopic structure, the community structure, one important mesoscopic description of network structure, is incorporated into network embedding in MNMF [Wang et al., 2017]. All the methods above mainly focus on preserving the pairwise proximity or community structure on a particular resolution, while the community structure at different scales are not considered.

Hierarchical Network. Many complex networks in the real world have hierarchical community structures. [Newman, 2003] introduces the community structure of the network, and summarizes that complex networks have the small-world property and the scale-free property. [Song et al., 2005] find that a large number of real networks have the self-similar property. Besides, the works on detection of hierarchial communities for networks with implicit hierarchical structure attract more attentions [Shen et al., 2009]. Recently, there are few researches on network embedding taking into account the hierarchical structures of networks. [Nickel and Kiela, 2017] uses the hyperbolic space to study the hierarchical structure of the network. The learned representation vectors are in the hyperbolic space, which are difficult to be converted into the Euclidean vectors. However, most of machine learning algorithms require the input vectors to be in the Euclidean space. Thus, it is necessary to study hierarchical structure preserving network embedding in the Euclidean space.

3 Galaxy Network EmbeddingModel

In this section, we introduce our notation, and formulate hierarchical preserving network embedding to preserve the pairwise proximity between communities and the hierarchical structure properties. Inspired by the galaxy structure, we introduce the Galaxy Network Embedding.

3.1 Notation

An undirected network G is denoted as (V,E), where V is the set of vertices and E is the set of edges. The hierarchical clustering tree of G is denoted as T with a depth of L. C denotes the node set and cli denotes the i-th node at the l-th level of T. Ch(c) denotes the child node set of the node c and pa(c) denotes the parent node of c. Meanwhile, cli also represents the i-th community while recursively dividing G at the l-th level. For the l-th level of T,

Especially, c11 is the root node of T and also the node set of G (i.e. c11 = V ) and cLi = {vi}, where vi is the i-th vertex of the G.

In order to preserve the hierarchical structure property of the network explicitly, we embed not only the vertices but also the communities of all layers. Due to cLi = {vi}, for brevity, we use the community representation instead of the vertex representation in the model.

We denote Φ(c) ∈ Rm as the representation of the community c, where m ≪ |C|. The problem of the hierarchical preserving network embedding is to learn the low-deminsional representations Φ of communities that can preserve the pairwise proximity between communities and the hierarchical structure properties.

3.2 Hierarchical Preserving Network Embedding

In our scenario, the community representation can preserve two kinds of properties of G. One is the local information, i.e. the pairwise proximity between sub-communities in the same community at a certain layer. The other is the hierarchical structure property, i.e. horizontal relationship and vertical relationship.

Pairwise Proximity Preservation

In order to preserve the local information between communities, we first define the community proximity Sk i,j extended from the definition of the common neighbor similarity [Libennowell and Kleinberg, 2007]:

which means the average common neighbor similarity between the community cli and clj , where A is the adjacency matrix of G and Au is the u-th column of the A.

We extend LINE with Second-order Proximity [Tang et al., 2015] to define a local objective for the communities deriving from the same parent node cl-1 k , namely,

which minimizes the KL-divergence between the distribution of community proximity from the ground truth and from the learned representation respectively. P(Φ′ (clj ) |Φ(cli )) is modeled by the softmax function, i.e.

where Φ(c) is the representation of c and Φ′ (c) is an auxiliary vector defined in LINE. Considering the computational efficiency, we approximate the softmax function using negative sampling [Mikolov et al., 2013b].

Hierarchical Structure Preservation

Besides the pairwise proximity, the community representations should preserve the hierarchical structure property. In detail, two relationships should be preserved in the hierarchical tree:

Horizontal relationship: nodes belonging to the same community should be closer to each other than those belonging to different communities in a certain layer, which can be illustrated with the following equation in Euclidean space: For all l = 1, . . . ,L, for all clu , clv ∈ C l with pa(clu ) = pa(clv ), for all clw ∈ C l with pa(clu ) ̸= pa(clw ), we have

where ‖·‖ means 2-norm.

Vertical relationship: the cohesion degree of shallower layer communities should be smaller than that of deeper layer ones in T. Naturally, the cohesion degree of a community can be represented by the average representations distance between the sub-communities in it. Thus, the parent-child relationship can be described with the following equation: For all l = 1, . . . ,L- 1, for all cl-1 k ∈ C l-1 , for all cl+1 i ∈ Ch(clj ) and all clj ∈ Ch(cl-1 k ), we have

Considering the pairwise proximity preservation (Eq.(2)) and hierarchical structure preservation (horizontal Eq.(3), vertical Eq.(4)), we introduce Galaxy Network Embedding to learn the representations of nodes in hierarchical tree.

3.3 Galaxy Network Embedding

As discussed in the introduction, we resemble the galactic hierarchical structure to use sphere embedding for sibling nodes in the hierarchical structure. This leads to the following GNE optimization formulation:

The rl-1 k in the above formulation denotes the sphere radius of the community cl-1 k , to reflect the spherical embedding where all children nodes of cl-1 k are embedded at a sphere of radius rl-1 k centered at cl-1 k . The radius rli of the community cli is obtained by the following strategy:

and pa(cli ) = cl-1 k , η is an arbitrary positive real number less than 1 6 . Especially�dl-1 k is determined when calculating rli .

In this way, we can optimize the objective Eq.(5) recursively from top to bottom in hierarchy to preserve the pairwise proximity and the hierarchical structure. The whole embedding procedure is illustrated in Fig.2. Obviously, the pairwise proximity can be preserved with the GNE objective Eq.(5). Next, we introduce Lemma.1 to prove the hierarchical structure can be preserved with Eq.(5).

Lemma 1. The community representations learned from recursively optimizing the Objective Eq.(5) with the strategy Eq.(6) preserve the constraints Eq.(3) and Eq.(4).

Proof. According to Eq.(5) and Eq.(6): for any cli ∈ C,

where pa(cli ) = cl-1 k .

For any nodes clu , clv and clw at layer l, where pa(clu ) = pa(clv ) and pa(clu ) ̸= pa(clw ). cτ-1 k is the common ancestor of clu and clw . Besides, the cτ-1 k 's children cτi and cτj are ancestors of the clu and clw , respectively. Thus, according to the constraints in Eq.(5) and Eq.(8):

where, P(cτi , clu ) is a set of nodes in all paths from cτi to clu in the hierarchical tree, cτi ∈ P(cτi , clu ) and clu /∈ P(cτi , clu )

According to Eq.(7)�

Thus,

Further, we can obtain the following relationship according to Eq.(6) and Eq.(8)�

where, Finally, we can obtain

Thus, we prove the community representations learned from GNE can preserve the horizontal relationship in hierarchy. Similarly, we can prove that the vertical relationship can be also preserved and we don't repeat it in the paper.

4 Learning Procedure of GNE

In this section, we introduce the learning algorithm of GNE, including how to solve the optimization problem Eq.(5) layer by layer and the pseudocode of GNE. Compared with the optimization objective of the classic neural embedding method, we just add an extra spherical constraint in Eq.(5). The neural embedding method can be directly optimized using SGD, which is efficient and the effect of which has been verified. Considering these advantages, we transform Eq.(5) into a two-step optimization procedure. First, we use the Adam optimizer to optimize Eq.(2) without constraint based on neural networks, and obtain the intermediate representation Ω(cli ) of communities that preserves the pairwise relationship of communities. Second, we map Ω(cli ) to a spherical surface to get the final representation Φ(cli ) of communities. Next, we introduce the spherical projection method.

4.1 Spherical Projection

To preserve the relative distances in spherical projection, we formally define the following optimization objective:

where,

The first term is to preserve the relative distances, and the second term is a penalty term to make the distances between each pair of points after projection are as large as possible. µ and γ are hyper parameters. As the overall optimization procedure is top-down, Φ(cl-1 k ), rl-1 k andD are all constants.

Spherical Projection Optimization Procedure

The constraints of Eq.(9) are for arbitrary spherical surfaces. We can perform scaling and translation transformations on the coordinate system to turn them into the unit sphere constraints, namely the following conversion :

Combining with Eq.(10), the Euclidean distance between Ψ(cli ) and Ψ(clj ) can be expanded as follows:

It can be seen that B′ij is not related to the length of vector Ψ(cli ) and Ψ(clj ), but only the cosine distance between them. Therefore, the vector length constraint in the objective can be removed. The final optimization objective on the unit sphere is:

We use Ψ∗(cli ) to denote the minimum point after optimization. After normalization, translation, and scaling, the final results are obtained:

Obviously, the unconstrained objective has a lower bound that can be found using Gradient Descent algorithm.

4.2 The GNE Algorithm

The pseudocode for GNE, is given in Algorithm 1. The whole embedding process is executed from top to down. For all children nodes of a certain node cli , i.e. the nodes in Ch(cli ), the learned representation Ψ(Ch(cli )) on the unit sphere can be obtain after two-step optimization procedure with Adam, the optimization Eq.(2) is used first and the optimization Eq.(12) follows. The final representation Φ(cl+1 j ) can be obtained by the transformation in Eq.(13). Besides, the corresponding rl+1 j can be calculated with the minimum distance dj,∗. The constant η less than 1 6 (see Lemma 1), so η = 17 in our experiments.

Algorithm 1 The GNE algorithm

function LEARNFEATURES(Network G, Hierarchical Clustering Tree T )

Initialize Φ(c11 ) = 0 and r11 = 1

Φ = RecursiveOptimization (c11 , G, T , r, Φ)

return Φ

function RECURSIVEOPTIMIZATION(Current node cli , Network G, Hierachical Clustering Tree T , Radius Set r, Reresentation Set Φ)

return Φ

Time Complexity Analysis

For brevity of description, we assume that the hierarchical clustering tree of network G = (V,E) is a k-ary tree T with depth logK|V |. The number of nodes N in T is KlogK|V |+1-1 K-1 . Spherical embedding should be done on each tree node layer by layer. Especially, the embedding procedures on the same layer tree nodes can be parallelized. For spherical embedding, the complexity of computing Ω(Ch(cli )) is O(EKQ). More precisely, E is the number of training epoch, K is the size of community to be embedded and Q is the neural network computing complexity of skip-gram model, i.e. Q = O(C(D + DM)), where C is the skip window size, D is the embedding size and M is the negative sampling size; the complexity of computing Ψ(Ch(cli )) is O(EK2D). Thus, the spherical embedding complexity is O(EKQ + EK2D). The optimization algorithm is implemented on the Tensorflow platform, which can be accelerated with GPU.

5 Experiments

In this section, we present our experimental evaluation of the GNE method on both synthetic and real networks.

5.1 Experiment Setup

Data Sets We employ the following three real datasets in the Facebook social networks dataset which comprises 100 colleges and universities in US [Traud et al., 2012]. We choose the social networks in Hamilton University (2314 nodes, 96394 edges), Amherst College (2235nodes, 90954edges) and Georgetown Universit (9414 nodes, 425639 edges). Moreover, in order to evaluate the performance of hierarchical community structure preservation, four Hierarchical Random Graphs (HRG) with explicit hierarchical community structure are generated by [Clauset et al., 2008], i.e. Syn with 125nodes (125 nodes, 406 edges), Syn with 1800nodes (1800nodes, 739637 edges), Syn with 2560nodes (2560 nodes, 1460147 edges) and Syn with 3750nodes (3750 nodes, 3066250 edges).

Relevant Algorithms We compare the GNE against six network embedding algorithms: SpectralClustering [Tang and Liu, 2011], DeepWalk [Perozzi et al., 2014], Node2Vec [Grover and Leskovec, 2016], LINE [Tang et al., 2015], GraRep [Cao et al., 2015] and MNMF [Wang et al., 2017].

Parameters Settings The hyper-parameters of GNE is θ, i.e. θ = (µ, γ). GNE is not very sensitive to the hyperparameters, the settings of which can achieve ideal results with grid search on a small range. In our experiments, the embedding size m of all models is 64. Besides, the parameter setting of comparison models follow the recommended settings in relevant code packages.

5.2 Hierarchical Community Detection

In this section, we verify the ability of hierarchical community preservation of our model GNE. We consider synthetic data sets in this experiment, including three different structures of HRG but with the same number of layers (see Fig.3). Jaccard's coefficient is applied as an external index for evaluating the performance of community preservation at each hierarchy of networks.

Fig.3 shows that the content of the hierarchical community structure can be integrally preserved with our model, no matter how many communities are there. However, MNMF only preserves community information at some layers but not all, and its performance is inferior to GNE, while other models perform much worse and could not handle multi-layer and complex community structure well.

5.3 Network Visualization

Network visualization is an important application of network embedding, and it maps a network into the two-dimensional space. We visualize a synthetic network with 125 nodes, 406 edges and 5 communities. Fig.4 presents the visualization experiments. We firstly generate a self-similar network of which nodes are derived from the leaves of five-ary tree with four layers and edges are derived from the sampling of connected paths between leaves in the tree. Additionally, the vertices in the network are classified into different communities with GirvanNewman algorithm [Girvan and Newman, 2002]. We compare our method against other models. For other models, we layout the network into low-dimensional space, and then further map the low-dimensional vectors of the vertices to a 2-D space with t-SNE package [Maaten and Hinton, 2008]. For our model, we can directly embed network into 2-D vector space based on our spherical embedding we proposed.

It can be seen from Fig.4 that our model GNE embeds vertices on the different-scaled spherical surface hierarchically. It is evident that the vertex representations of GNE are consistent with modularity property at each hierarchy, i.e. higher intra-cluster similarity but lower inter-cluster similarity. That is to say, GNE integrally preserves the hierarchical community structure. Additionally, GNE has an outstanding performance on clustering vertices compared with others.

5.4 Vertex Classification

In order to verify the effectiveness of GNE on vertex classification, three real social networks of the Facebook datasets with the four-layer hierarchical tree (including root and leaves) are used. The two intermediate layers are divided by the enrollment year and major, respectively. For MNMF, we use enrollment year as an indicator for community division. The learned representations are used to classify the vertices into a set of labels. The classifier we used is Logistic Regression with sklearn package, and the evaluation metric is Accuracy. Different percentage of nodes are sampled randomly for evaluation, and the rest are for training. The results are averaged over 10 different runs.

Table 1 shows that GNE almost always performs the best among all models on different percentage of test data size. Our model is also robust across different percentage of test datasets.

6 Conclusion

In this paper, we propose Galaxy Network Embedding (GNE) for network embedding to preserve the hierarchical community structure of a network. Specifically, we introduce an optimization problem with constraints and transform it into an unconstrained optimization problem more easily to be solved. Moreover, we propose a spherical embedding method to maintain the hierarchical community structure from top to bottom. Empirically, we verify GNE in a variety of network datasets and applications. The extensive experimental results on vertex clustering and classification, as well as network visualization, demonstrate the advantages of GNE, especially on the networks with hierarchical community structures.

Acknowledgments

We are thankful to Yizhou Sun for her helpful suggestions. This work was supported by the National Natural Science Foundation of China (Grant No. 61572041 and No. 61433014)