Efficient Attributed Network Embedding via Recursive Randomized Hashing

1 Introduction

The surge of real-world network data, e.g., citation networks and social networks, has fostered network mining research. An important research that underpins many high-level applications is to represent the network by embedding each node in the network into a low-dimensional space. Based on the simplified network representation (i.e, network embedding), one can conduct node classification [Bhagat et al., 2011] and link prediction [Liben-Nowell and Kleinberg, 2007], etc. In some real-world scenarios, high efficiency is strongly required with precisions guaranteed. For example, given an evolving social network, if we aim to retrieve the most similar users w.r.t. a queried user (e.g., for user search or friend recommendation), network representation should be performed very quickly to return precise results. Therefore, it is necessary to develop efficient and effective network embedding algorithms.

Recently, various network embedding algorithms have been proposed, including plain network embedding methods with only structure information preserved [Perozzi et al., 2014; Grover and Leskovec, 2016], and attributed network embedding approaches with both structure and content information captured [Huang et al., 2017a; 2017b]. However, plain network embedding methods may not satisfy accuracy because content information is simply ignored, while attributed network embedding methods usually involve inefficient learning procedures due to massive matrix operations.

To preserve content and structure information and dramatically reduce the computational cost in situations without powerful workhorses (e.g, query in mobile devices), one possible solution is to employ randomized hashing techniques [Broder et al., 1998; Gionis et al., 1999; Chi et al., 2014; Wu et al., 2016; 2017; Yang et al., 2017], which can efficiently sketch high-dimensional data and map them into a fixed number of dimensions as an estimator. Some hashing algorithms have been used to characterize substructures in the graph, e.g., [Gibson et al., 2005] discovers large dense subgraphs. By contrast, in [Li et al., 2012], the graph is represented as a feature vector, where each dimension comprises a set of substructures, for classification by employing the hashing techniques to approximately count substructures.

Although there have been some research using randomized hashing techniques to approximately count substructures in a graph as features, to our knowledge there is no reported work using randomized hashing for graph embedding (node representation). In this paper, we represent each node of a graph as a shallow rooted tree through expanding its neighboring nodes, and then adopt the Locality-Sensitive Hashing (LSH) algorithm to sketch level-wise content of the rooted tree from bottom (the predefined highest-order neighboring nodes) to top (i.e., the root node). In particular, to summarize multiple attributes at each level of the rooted tree, MinHash, which is a well-known randomized LSH scheme in the bag-of-words model, is recursively employed. In the recursive operation of LSH along the rooted tree, we take into account the law of network information diffusion, i.e., exponential decay from the information source to the distance. This implies that the proposed recursive randomized hashing algorithm should be able to discount the content information level by level in the course of propagation. We name the resulting algorithm for attributed network embedding NetHash, which can encode the attributes and structure information of the attributed network for each node using a low-dimensional discrete vector.

We provide theoretical analysis of the estimator of the similarity between two rooted trees, and also empirically evaluate effectiveness and efficiency of NetHash and the state-ofthe-art methods on a number of real-world citation network and social network data sets for the tasks of multi-class node classification, link prediction and large-scale node query. In summary, our contributions are three-fold:

1. This work is the first endeavor to introduce randomized hashing techniques into attributed network embedding.
2. We propose a novel non-learning attributed network embedding algorithm named NetHash, which can efficiently preserve content and structure information for each node by expanding the node and its neighboring nodes into a rooted tree and recursively sketching the rooted tree from bottom to top.
3. The experimental results show that NetHash can achieve competitive or better accuracy with significantly reduced computational cost, compared to the state-of-theart learning-based network embedding methods.

The remainder of the paper is organized as follows: Section 2 reviews related work of network embedding and graph hashing. Section 3 introduces the attributed network embedding problem. We describe NetHash in Section 4. The experimental results are presented in Section 5. Finally, we conclude this paper in Section 6.

2 RelatedWork

2.1 Network Embedding

Current network embedding approaches consist of plain network embedding and attributed network embedding [Zhang et al., 2017]. The former describes each node by considering only structure information in the network, while the latter preserves both content and structure information.

Inspired by Skip-Gram [Mikolov et al., 2013], DeepWalk [Perozzi et al., 2014] and node2vec [Grover and Leskovec, 2016] perform random walks in the network so that the nodes in the random walks can capture contextual structure information. The former uniformly samples nodes from neighbors in the random walk, while the latter non-uniformly does. On the other hand, The first-order proximity composed of edges between nodes preserves local structure information, and the second-order proximity shows that nodes with shared neighbors are similar and captures global structure information. LINE [Tang et al., 2015] explicitly defines an objective function to capture the two categories of structure information.

To incorporate content information, researchers have successively proposed attributed network embedding algorithms. TADW [Yang et al., 2015], as the first approach to attributed network embedding, injects texts into matrix factorization by proving that DeepWalk is equivalent to matrix factorization. Based on TADW, HSCA [Zhang et al., 2016] adds information of the first-order proximity to improve network representation. In addition to content and structure information, one node may have different contexts when interacting with different neighboring nodes. To this end, CANE [Tu et al., 2017] adopts deep learning to capture such contexts.

2.2 Graph Hashing

Although most randomized hashing algorithms are designed for vectors or sets, some works aim to capture structure information by characterizing substructures in the graph. In [Gibson et al., 2005], large dense subgraphs in massive graphs are identified by a variant of MinHash, where each hash function is generalized to return multiple elements to capture more neighboring information. In [Becchetti et al., 2010], a slight modification of MinHash, which accelerates the standard method, is used to estimate the local number of triangles in large graphs. Some works adopt two random hashing schemes: In [Chi et al., 2013], the first hashing scheme compresses a graph into a small graph, and the second one maps unlimitedly emerging cliques into a fixed-size clique set.

[Li et al., 2012; Wu et al., 2018] hash tree structures in the graph and approximately count substructures. Consequently, the graph is represented as a feature vector for classification, where each dimension comprises a set of substructures and the value of each dimension is related to the estimated number of the substructures. These algorithms cannot embed network nodes into a low-dimensional space, thus are not designed for node representation in our problem setting.

3 ProblemDefinition

Given an attributed network G = (V, E, f), where V denotes nodes of the network, E denotes undirected edges of the network, and f : V ↦→ A is a function that assigns attributes from an attribute set (or a global vocabulary) A to the nodes. Naturally, a node v ∈ V, which owns attributes f(v), can be represented as a 0/1 feature vector vv where each dimension represents an attribute in A. Figure 1(a) shows a toy example where an attributed network is composed of 6 nodes, 8 edges and 10 attributes. Each node is represented as a 10dimensional 0/1 feature vector (bottom right). Given a network G, we aim to embed each node vv ∈ {0, 1}|A| into a low-dimensional vector xv ∈ RK , where K ≪ |A|1 .

4 NetHash

In this section, we first introduce MinHash, and then propose the NetHash algorithm for attributed network embedding.

4.1 The MinHash Scheme

Given a universal set U and a subset S ⊆ U, MinHash is generated: Assuming a set of K random permutations, {πk}Kk=1 , where πk : U ↦→ U, are applied to U, elements in S which lie in the first position of each permutation, {min (πk(S))}Kk=1 , will be the MinHashes of S [Broder et al., 1998].

MinHash is an approximate algorithm to compute the Jaccard similarity of two sets. It is proved that the probability of two sets, S1 and S2, to generate the same MinHash value is exactly equal to the Jaccard similarity of the two sets:

1 Most algorithms embed nodes into l2 space, while we embed nodes into l1 space, as in [Gionis et al., 1999].

Algorithm 1 The NetHash Algorithm

Input: G = (V, E, f); number of embedding dimensions K; entropy of degrees of network S; depth of tree D 1 ; hash functions at the l-th level {π(l) k }D,kl l=0,k=1 Output: G's embedding h 1: for r = 1, . . . , |V| do 2: Build a parent pointer tree T for node r; 3: Initialize an empty auxiliary queue Q; 4: for v ∈ T ↑ do 5: l ← level of v inT; 6: merger ← f(v); // initial merger from attributes on v 7: while Q is not empty and v is the parent node of Q[0] in T do 8: merger ← merge(Q.pop().digest, merger); 9: end while 10: digest ← MinHash(merger, {π(l) k }kl k=1 ); 11: Q. push({digest, v}); 12: end for 13: h(r) ←Q.pop().digest; 14: end for

"merger", whose entries of 1 correspond to attributes or digests, e.g., [0 1 1 0 1 1 0 0 0 1] on Node 2 in Figure 1(d). Consequently, the internal node carries both its own and diffused content information. Essentially, this step preserves structure information by diffusing and merging because the structure (i.e., edges) is reflected by digests. Note that no merging operation occurs on leaf nodes. Finally, the root node returns its representation (Line 13).

4.3 Exponentially Decayed Diffusion

We build a framework of capturing content and structure information by recursively sketching the rooted tree. Intuitively, the lower-order neighboring nodes contribute more to representation of the root node than the higher-order ones do, which implies that NetHash should discount content information level by level in the course of propagation. To this end, we combine the recursive operation of the MinHash algorithm with the law of network information diffusion, i.e., exponential decay from the information source to the distance. Natually, the number of MinHashes, kl, which is the amount of digest produced from a node at the l-th level, satisfies:

1 Note that D = 0 indicates that the tree has only one root node.

We can conduct multiple independent random permutations for unbiasedly estimating the similarity:

However, the explicit random permutations are expensive. In practice, a hash function as follows can be used to generate the permutated index πk(i) = mod((aki + bk), ck ), where i is the index of an element from the universal set U, 0 < ak, bk < ck are two random integers and ck is a big prime number such that ck ≥ |U| [Broder et al., 1998].

4.2 The NetHash Algorithm

To simultaneously capture content and structure information in the network, we expand each node along with its neighboring nodes into a rooted tree. By recursively sketching the rooted tree from bottom to top, NetHash diffuses content information level by level. To this end, we employ the structure of parent pointer tree (PPT) to store the tree such that each node of the tree is visited only once. Figure 1(b) shows a tree rooted at Node 1 with depth 2. The 1st level has Nodes 2, 3 and 6, and the 2nd level has Nodes {1, 3}, {1, 2, 4, 5}, and {1, 5}. Figure 1(c) shows the corresponding PPT, which is a 12 × 3 array: The first column shows node identifiers on the network; the second column points to the parent node in the array, e.g., "-1" means that root Node 1 has no parent node and "1" in the 2nd row (i.e., [2, 1, 1]) shows that the parent node of Node 2 is in the 1st row (i.e., Node 1); the third column is the level where the node is located.

We outline NetHash in Algorithm 1. NetHash processes nodes one by one (Line 1). We first build the PPT to store the rooted tree whose root node is currently being processed (Line 2). Also, we introduce an auxiliary queue Q to store the currently visited node in the rooted tree and the corresponding diffused content information (Line 3). Subsequently, NetHash traverses the PPT from end to head (Lines 4-12). The recursive sketching process consists of two steps. Sketching a node produces a set of MinHashes called "digest", which represents the content information diffused from the node to its parent node, e.g., {b, j} produced by sketching Node 2 in Figure 1(d). Actually, the step summarizes content information of each node. In the while loop, an internal node merges its own attributes with all digests, which are generated by sketching its all child nodes, to produce the where K is the number of embedding dimensions, i.e., the number of MinHashes at the root node (its level is 0 and k0 = K), λ is the exponential decay rate, and int is a rounding function. If kl < 1, one attribute of digest will be diffused.

Content information is diffused along edges, so information diffusion is closely related to node degrees. If treating node degrees in a network as a distribution, we can define the entropy of node degrees, S, from the perspective of information theory: S = - ∑ν∈unique({νv}v∈V) Pr(ν) log Pr(ν), where νv is degree of node v and unique({νv}v∈V) is the set of unique degrees observed in the network. A large entropy suggests that the network tends to have evenly distributed degrees, which implies that content information diffused in the network is unstable since the amount of diffused content (in our case the "digest") varies widely from node to node. For example: Given a network containing 100 nodes, node degrees vary from 1 to 5, and the number of the nodes corresponding to each node degree, if evenly distributed, is 20. In this case, the amount of digest is different from node to node. The total amount of digest received by each node remarkably changes due to different degrees. If node degrees are not that evenly distributed and are more concentrated, the total amount of digest will tend to be consistent. To address the issue, such a network ought to diffuse little digest by accelerating the decay of diffusion. To this end, we use entropy as the decay rate and Eq. (1) is rewritten as

4.4 Theoretical Analysis

Similarity: Given two rooted trees, A(D) and B(D) , where D is the depth of the trees, their similarity is:

where X ∈ {A, B}, f (X (d) ∗ ) and π(d) (f(X (d) ∗ )) are attributes of all nodes at the d-th level and the digest sets produced from the corresponding nodes by MinHash π(d) at the d-th level, respectively, and the number of π(0) is K.

Bounds: We give bounds between the real similarity J(A(D) , B(D) ) and the estimated similarity ˆ J (A(D) , B(D) ).

Theorem 1 Given K > 2δ-2 s-1 log ϵ-1 , 0 < δ < 1 and ϵ > 0, for two rooted trees, A(D) and B(D) , we have bounds:

1. If J(A(D) , B(D) ) ≥ s, then ˆ J(A(D) , B(D) ) ≥ (1 - δ)s with a probability at least 1 - ϵ.
2. If J(A(D) , B(D) ) ≤ s, then ˆ J(A(D) , B(D) ) ≤ (1 + δ)s with a probability at least 1 - ϵ.

Proof 1 Let Xπ(0) ,··· ,π(D) be a random variable. Xπ(0) ,··· ,π(D) = 1 if ρ(A) = ρ(B), and 0 otherwise. Let X = ∑Kk=1 X(k) π(0) ,··· ,π(D) . Eπ(0) ,··· ,π(D) [X(k) π(0) ,··· ,π(D) ] = J(A(D) , B(D) ) ≥ s; E[X] ≥ Ks as only K MinHash functions sketch the root node whatever D is. Based on the Chernoff bound [Chernoff, 1952], we have

|V|: number of nodes; |E|: number of edges; ν: average node degrees; |A|: size of the attribute set; |A|: average number of node attributes; S: entropy of node degrees; |L|: number of node labels.

Table 1: Summary of the five network data sets.

Substituting Eq. (3) with ˆ J(A(D) , B(D) ) = XK gives

By rearranging Eq. (4), we prove the first proposition for K > 2δ-2 s-1 log ϵ-1 . Similarly, the second one is proved.

Complexity: The rooted tree can be averagely considered as a ν-ary tree, where ν and |A| denote the mean value of degrees of the network and the mean number of attributes of each node, respectively. Since NetHash traverses each node only once, the theoretical computational complexity is O(|V |( ∑D-1 d=0 (|A| + kd+1ν)kdν d + |A|kDνD )). Considering the simplified version of Eq. (2), i.e., kd = Ke-dS , we have O(|V |νDKe-DS (max{|A|, Ke-(D-1)S })).

TADW and HSCA first spend O(|V|2 ) in probability that each node randomly walks to any one in fixed steps; then in each iteration of the learning process, TADW costs at least O(|V|K2 + |V||A|K), and HSCA does at least O(|V|K2 + |V||A|K + |V||A|2 ). In practice, we normally consider trees with D ∈ {1, 2, 3} as the distant nodes can hardly diffuse effective attributes to the root node. Besides, in most networks, ν, νD ≪ |V| due to sparsity, |A|,K ≪ |A|. Therefore, the time complexity of NetHash is practically efficient, especially in large-scale networks since it is linear with respect to |V|.

5 Experimental Results

In this section, we evaluate the performance of NetHash via node classification, link prediction and node retrieval.

The state-of-the-art methods: (1) DeepWalk [Perozzi et al., 2014]: It captures contextual structure information based on random walks; (2) node2vec [Grover and Leskovec, 2016]: It performs a biased DeepWalk to explore diverse neighbors; (3) TADW [Yang et al., 2015]: It learns node representations by combining attributes with structure in matrix factorization; (4) HSCA [Zhang et al., 2016]: It adds the firstorder proximity to TADW; (5) CANE [Tu et al., 2017]: Besides attribute and structure information, it captures different contexts which a node expresses for different neighbors.

Data sets: (1) Cora [Yang et al., 2015]: A citation network of machine learning papers. (2) Wikipedia [Yang et al., 2015]: A citation network of articles in Wikipedia. (3) Flickr [Li et al., 2015]: The network consists of users as nodes, following relationship as edges and interest tags of users as attributes. (4) BlogCatalog [Li et al., 2015]: The network consists of bloggers as nodes, following relationship as edges and keywords in blog as attributes. (5) ACM [Tang et al., 2008]: The original data contains 2,381,688 ACM papers and 10,476,564 citation relationship. After cleaning up papers without abstracts or citations, we build a citation network with papers as nodes, citation as edges and abstract as attributes. The data sets are summarized in Table 1.

Table 3: Link prediction results on social networks.

Experimental Settings: For all methods, we set the embedding dimension K = 200, as in TADW and CANE. All compared algorithms are implemented by the authors and their parameters are set to default values. For two nodes v1 and v2, NetHash generates the representations of length K, xv1 and xv2 , respectively. The Jaccard similarity between xv1 and xv2 is Simxv1 ,xv2 = ∑Kk=1 1(xv1,k=xv2,k) K . The runtime of NetHash consists of generating hash functions, constructing and sketching the rooted trees. All experiments are conducted on a node of Linux Cluster with 8 × 3.4 GHz Intel Xeon CPU (64 bit) and 32GB RAM.

5.1 Node Classification on Citation Networks

We report classification performance on Cora and Wikipedia. In the task, we adopt LIBSVM [Chang and Lin, 2011] for NetHash which uses the Jaccard similarity matrix as the precomputed kernel, and LIBLINEAR [Fan et al., 2008] for the compared algorithms 2 , as used in their papers. We vary the training ratio (i.e., percentage of nodes as the training set) in

2 We test the compared methods on LIBSVM. DeepWalk, node2vec and CANE achieve similar accuracy while TADW and HSCA perform worse, so we just report results on LIBLINEAR.

{50%, 60%, 70%, 80%, 90%}, for each ratio of which we repeat the experiment 10 times and average the results.

Table 2 reports the experimental results in accuracy (Micro-F1 and Macro-F1) and runtime. NetHash defeats all plain network embedding algorithms, and achieves the competitive and even better accuracy than all attributed network embedding ones. In runtime, NetHash presents the strong advantage: it performs more efficiently than all compared methods. Generally, NetHash outperforms TADW and HSCA by one to two orders of magnitudes, and CANE by four orders.

5.2 Link Prediction on Social Networks

We conduct link prediction task on Flickr and BlogCatalog. NetHash uses the Jaccard similarity in l1 space while the compared methods does the Euclidean distance in l2 space (the same in Section 5.3). A training network is obtained by randomly preserving a training ratio of edges, while the removed edges act as the unobserved (test) links. Based on the training network, we compute similarity between each pair of nodes. Then, we randomly pick an unobserved link and a nonexistent one to compare their similarities. AUC values represent the probability that a randomly selected unobserved link is more similar than a randomly selected nonexistent one by repeating the picking operation 10,000 times. We compute AUC values 10 times and average the results.

Table 3 shows the experimental results of AUC and runtime. NetHash significantly outperforms the compared methods in AUC and runtime on Flickr, and it defeats all attributed network embedding algorithms on BlogCatalog. NetHash exhibits superiority in runtime - it performs much more efficiently than the compared methods by orders of magnitudes.

Table 4: Top-5 Query results on a large-scale citation network.

5.3 Case Study: Node Retrieval on a Large-scale Citation Network

In this case study, given 5 query papers on ACM that have top 5 highest citation numbers, we retrieve 5 most similar papers for each query based on their embeddings. Due to similar results and space constraint, we only report the result of the paper with the highest citation number (i.e., 6,294).

Table 4 presents the query result. All results retrieved by NetHash are closely related to algorithms and machine learning and particularly, it accurately returns one paper regarding the genetic algorithm (i.e, the third result). Moreover, from the semantic perspective, we find that the results, except the third one, and the query all focus on topics of AI and algorithms, while the papers retrieved by DeepWalk are more related to specific applications, which deviate from the query. In terms of runtime, NetHash is still very efficient when running on such a large-scale network data.

5.4 Discussion on the Results

In the above three tasks, NetHash generally achieves competitive and even better accuracy, because it preserves both content and structure information while DeepWalk and node2vec only capture structure infomration. Exceptionally, DeepWalk performs best on BlogCatalog, largely because it captures sufficient structure information by long random walks in the complex network (e.g., large average node degree and entropy). In terms of attributed network embedding algorithms, NetHash and TADW essentially preserve attributes and structure information, so they keep the same level in accuracy on Cora, Wikipedia and BlogCatalog; the reason why NetHash defeats TADW on Flickr is largely because the recursive operation of MinHash can more effectively capture structure information. Although HSCA and CANE additionally capture first-order proximity and contexts, respectively, NetHash still outperforms them on Wikipedia, Flickr and BlogCatalog because the additional information negatively impacts representation and in turn deteriorates the accuracy.

In terms of runtime, NetHash performs much more efficiently than DeepWalk and node2vec, because NetHash expands nodes into the trees with the depth being around 2 while DeepWalk and node2vec perform long random walks. We know from Section 4.4 that empirically, NetHash has lower time complexity than TADW and HSCA. CANE experimentally executes a substantial number of matrix operations in deep learning, which is costly in runtime and demands powerful workhorses. In addition, NetHash, as a randomized algorithm, avoids the iteration process in the learning-based algorithms, which is also an important factor of high efficiency.

5.5 Parameter Sensitivity

NetHash has two exclusive parameters, tree depth D and decay rate λ. Due to space constraint, we report only the node classification results on Cora.

Table 5 (top) shows accuracy of NetHash w.r.t. tree depth D. NetHash achieves the best accuracy on Cora when D = 2. The reason why the accuracy on Cora improves first when D varies from 1 to 2 is largely because more useful attributes are captured from higher-order neighboring nodes. However, when D further increases to 3, more noise will dominate in the diffusion process to deteriorate the performance, which generates the unsatisfying representation. Thus, tuning depth D is a tradeoff between noise and useful attributes, and the optimal value of D depends on the particular data. The runtime grows with D increasing. We set D = 1 for Wikipedia, Flickr and BlogCatalog, and D = 2 for Cora and ACM.

Table 5 (bottom) shows accuracy of NetHash w.r.t. exponential decay λ. The accuracy first increases and then declines. The best accuracy is achieved when λ is set to the entropy of node degrees S. A smaller λ implies more diffused information and thus, more noise; while a larger λ implies less diffused information, which is insufficient. The runtime decreases remarkably with λ increasing. Hence, we adopt the entropy of node degrees S as the decay rate.

6 Conclusion

In this paper, we propose an efficient attributed network embedding algorithm dubbed NetHash, which employs the randomized hashing technique to recursively sketch the shallow trees, each of which is rooted at a node of the network, from bottom to top, and preserves as much information closer to the root node as possible by simulating the exponential decay in network information diffusion.

We conduct extensive empirical tests of NetHash and the state-of-the-art methods on five network data sets. The experimental results show that NetHash not only achieves competitive or better performance but also performs much faster than the compared methods by orders of magnitude. In large-scale network analysis, NetHash can perform very well with a limited budget of computational capacity, which makes it more practical in the era of big data.

Acknowledgments

This work is partially supported by ARC Discovery Grant DP 180100966. Bin Li is supported by the Fudan University Startup Research Grant (SXH2301005) and Shanghai Municipal Science & Technology Commission (16JC1420401).