In the Big Data era, large graph datasets are becoming increasingly popular due to their capability to integrate and interconnect large sources of data in many fields, e.g., social media, biology, communication networks, etc. Graph representation learning is a flexible tool that automatically extracts features from a graph node. These features can be directly used for machine learning tasks. Graph representation learning approaches producing features preserving the structural information of the graphs are still an open problem, especially in the context of large-scale graphs. In this paper, we propose a new fast and scalable structural representation learning approach called SparseStruct. Our approach uses a sparse internal representation for each node, and we formally proved its ability to preserve structural information. Thanks to a light-weight algorithm where each iteration costs only linear time in the number of the edges, SparseStruct is able to easily process large graphs. In addition, it provides improvements in comparison with state of the art in terms of prediction and classification accuracy by also providing strong robustness to noise data.
g c e d b h f
More specifically, a graph node representation associates to each graph node a vector of hidden features. We consider only representation learning models trained with an unsupervised procedure that is independent to any specific machine learning task.
Unsupervised graph representation learning approaches are divided into connectivity and structure-based. Connectivity-based representation learning methods work on the assumption that nodes that are in proximity have similar representation, e.g., nodes and in Figure 1 are in proximity (it exists a short path connecting them) while nodes and are not. Instead, structural-based node representations assume that if two nodes have a similar structure, they should have the same representation, e.g., in Figure 1, nodes and are structurally identical even if they are not connected, the same for the nodes and .
Connectivity-based approaches are usually better for the task of edge prediction, while structural-based approaches are more suitable for node classification tasks [ 5]. This is because the structural representations helps the identification of structural patterns useful for the classification. Moreover, connectivity-based approaches in the case of two disconnected nodes (such as and ℎ) may have completely diferent representations even if, according to a specific classification task, these two nodes should have the same class.
The structural representation learning approaches already proposed in the literature, such as Struc2vec [5] and GraphWave [6], do not scale well on large graphs because their non linear execution time. In addition, as we show in our experimental section for some structural classification tasks, they sometimes present some poor performance. In this work, we propose a structural representation approach, called SparseStruct, that creates for each node a sparse representation that is condensed through a truncated singular value decomposition. The sparse representation is created with an iterative approach exploring the structure of a node, level by level. More specifically, this paper provides the following contributions: (i) we define SparseStruct, a structural representation learning approach with a convergent iterative procedure; (ii) we provide formal proof about the ability of SparseStruct to preserve the structural information of nodes; (iii) we prove that SparseStruct’s execution time is linear on the size of the graph; (iv) from the experimental results, SparseStruct in all the experimental cases is comparable or better than the other approaches considered in terms of performance for regression and classification tasks.
In this section, we first present a set of important notations and concepts that will be used throughout this work.
Let = ( , ) be a unlabeled undirected graph, or network, where denotes the set of nodes, and ⊆ ( × ) denotes the set of edges connecting the nodes in . | | and || denote the number of nodes and edges contained in the graph respectively. The neighborhood of any node ∈ is given by () = { |(, ) ∈ ( , ) ∈ } , and | ()| denotes the size of this neighborhood or the node’s degree. The diameter of a graph is commonly defined as the ”longest shortest path” between any two nodes of the graph. More formally, the diameter is the length (, )(, ) between any two graph nodes (, ) , where (, ) is the distance between nodes and .
The representation of a node is defined as ∈ ℝ , where k is the desired size of the representation. Finally, the whole representation matrix is defined as ∈ ℝ | |× . Graph representation learning methods require a notion of proximity between nodes in order to learn. These methods can, arguably, be classified into two groups based on the proximity notion they use, connectivity-based methods (K-order Proximity), and structure-based methods (Structural Role Proximity ) [7].
Dimensionality reduction approaches are used to reduce the size of a set of features. Truncated SVD [8] is a Linear dimensionality reduction using Singular Value Decomposition to reduce the dimension. Contrary to Principal Component Analysis [9], Truncated SVD does not center the data before computing the singular value decomposition. Such diference makes this approach suitable to work with sparse matrices.
Truncated SVD has been widely applied on text analysis applications [10]. It is known as latent semantic analysis (LSA), and it is applied to term-document matrices. The result of such transformation is a “semantic” space of low dimensionality that contrasts the efects of synonymy and polysemy, i.e. when there are multiple meanings for the same word. Truncated SVD is also used in graphs by transforming the sparse graph adjacency matrix [11]. This produces a connectivity-based graph representations. In our work, we will show how to efetely use the truncated SVD procedure with a newly defined sparse matrix to produce a structural graph representation learning procedure.
The fastest solver for Truncated SVD is based on a randomized approach [12]. The time complexity for this approach is ( × + ( + ) × 2), where is the size of the reduced dimensional space, is the execution time of the sparse matrix multiplication with a vector, is the number of rows in the sparse matrix, and is the number of columns.
In this section, we provide the details of SparseStruct, described in Algorithm 1, that learns a structural node representation. SparseStruct is divided into two steps: Step 1 (line 2) use an iterative procedure to create a sparse positive integer matrix where each row corresponds to a sparse vectorial representation of a specific node, and Step 2 (line 3) uses the Truncated SVD to transform the sparse matrix in a smaller dense representation with dimensions, ( represents the size of the learned output representation. The matrix (line 3) represents the output of our algorithm.
Intuitively, at each iteration of the process the algorithm determines the structural information of a generic node , by considering all the possible structure combinations present in the graph at depth . All these structures are indexed and used to describe a node’s structure in terms of its neighboring nodes structures. The concatenation of all the sparse matrix through a horizontal stacking tells how the structures connected to a node changes step by step with the increase of the exploration depth. This process runs until no more change is detected by the algorithm. For this reason, we called the maximum number of iteration ℎ (line 11). 13-15). Each matrix space is less than (||)
More specifically, in this algorithm, we assume that each node of the graph has a unique identifier ( )
from 0 to | | − 1 , and such identifier is the index of all the matrices (sparse and not) created in the algorithm. Then the final representation learned for a generic node is given by [(), ∶]
. The core part of Algorithm 1 is the iterative procedure that creates the structural representative sparse matrix , and it is inspired by the WeisfeilerLehman method for graph isomorphism testing [13]. At each iteration , the method assigns to all the identical rows the same progressive identifier with the use of a hash tree index (line 12), and then create a sparse matrix where the value of the generic cell is the number of neighbor nodes of that are indexed with the identifier (lines has dimension | | × | ( . Each generated sparse matrix )| however its occupied memory inside the while loop is added to the list (line 17), and after the while loop, all the sparse matrices in are horizontally stacked to create a unique sparse matrix called that is the output of the method.
The while loop (lines 11-25) iterates until the number of indexes generated (line 12) stops to grow at each iteration, or a maximum number of iterations is reached.
While this approach may, at first glance, seem space and time consuming depending on the number of iteration of the algorithm, in reality, we will show in the time and space complexities section that this is not the case. This is because of the fast convergence of our Theorem 1. Given a graph = ( , ) , for each pair of nodes (, ) having the same structure (i.e., the graphs extracted from a visit of and are isomorphic) the representations [(), ∶] and [( ), ∶]
are the same.
In the following subsections, we show: (i) the optimality of the stopping criterion, and (i) the time and space complexity of our proposed approach, that under certain conditions are algorithm. graph (see Theorem 1).
Our representation approach is able to preserve structural properties of the nodes in the
We describe the time and space complexities of Algorithm 1. The following theorem shows that, assuming the ℎ a constant, the method has space and execution time linear in the number of edges of the graph times the number of iterations. Consequently, considering the min( ℎ, ) as a constant, our proposed method is linear (in space and time) on the graph size.
Theorem 4. Let be the iteration when the function (in Algorithm 1) stops due to the condition in (line 18), the time and space complexity of the method in Algorithm 1 is (|| × min( ℎ, ))
The entire algorithm complexity depends on the cost to compute the sparse matrix plus the cost to apply the Truncated SVD on the aforementioned matrix. The following theorem gives an idea of the whole execution cost of the algorithm.
Theorem 5. Let be the iteration when the function the condition in (line 18), the execution time of Algorithm 1) is ((| |+||× 2) (in Algorithm 1) stops due to min( ℎ, ))×
It is important to note that the execution time for the Truncated SVD is a pessimistic upper bound, as mentioned in [7], and, in average the execution time is small. In term of space complexity of the entire approach we have still (| | + || × min( ℎ, )) .
In this section we present a set of experiments to empirically verify the capabilities of SparseStruct. We compare our approach with the following six well established techniques: node2vec [14], struc2vec [5], GraphWave [6], GraphSAGE [15], ARGA [16], and DRNE [17].
To test these approaches, we select a set of small to large-sized real-world graphs. They range from hundreds to thousands of nodes. The chosen graphs are: • Facebook348 [18]: This network is one of the ten available ego networks (id 348) of the
Stanford ego-Facebook dataset. The network contains 224 nodes and 3,192 edges. • Air-trafic networks [5]: In this set of networks, nodes represent airports and edges indicate the existence of commercial air trafic between them. We will use three diferent sized air-trafic networks: Brazilian air-trafic network (131 nodes and 1,038 edges), European air-trafic network (399 nodes and 5,995 edges), and American air-trafic network(1,190 nodes and 13,599 edges). • Wikipedia [14]: This network contains the co-occurrence of words appearing in the first million bytes of the Wikipedia dump. The network contains 4, 777 nodes and 184, 812 edges.
All experiments used an Intel Xeon E5-2620 2.00GHz CPU with 128 GB of RAM memory and an Nvidia GeForce GTX 1080 Ti GPU with 11 GB of dedicated memory. SparseStruct is implemented in python and for all the other methods, we used the Python implementation provided by the authors and, unless otherwise stated, default parameters provided in the code and their documentation.
To evaluate the structural information encoded inside the generated representations, we propose a set of regression-based experiments where we use our representations to extract known centrality metrics. We consider the following centrality metrics: PageRank (PR), HITS Authority/Hub, Degree Centrality (DC), Eigenvector Centrality (EC), Betweenness Centrality (BC), and Node Clique Number (NCN).
To do so, we compute all the node representations and network metrics to generate the feature datasets and the ground truths to train and test the regression models. For the regression task, we use Support Vector Machine regression [19], and the optimal hyper-parameters (including kernel type) are selected with a grid-search approach and 10-fold cross-validation. The performance metrics we use are the Root Mean Square Error (RMSE) and the Coeficient of Determination ( 2), obtained as the average value computed over the results of the 10-folds.
In Table 1 are reported the results of each metric for each dataset and for each representation learning approach. As a baseline, we considered the degree of each node since one 1 generated by the sparseMatrixGen method in Algorithm 1 contains the degree of each node. Note that the results for the degree in the case of the degree centrality are not reported since two are the same.
From Table 1,SparseStruct is often outperforming all the other representation learning techniques or produce comparable results.
We test and compare SparseStruct and all the other considered approach with the node classiifcation task. The node classification task consists in predicting a label for a set of unlabeled nodes. For these experiments, we selected the Brazilian, European, and American air-trafic networks from [5]. In order to test a structure-based classification setting, the datasets have been labeled according to each airport’s activity level, where each airport activity is measured by the total number of airplane landings and takeofs. Each airport on the datasets has been assigned with one of four possible activity levels. With these levels being the labels for our classification task. In order to assign each label, authors use the quartiles from the empirical airport activity distribution to split the dataset into four airport groups, each of these groups containing 25% of the total airports. The labels are ordered in increasing activity order, where group 1 contains airports with the least activity, and group 4 contains airports with the most activity. The resulting groups are used to label each node in the datasets. This process has been applied to each dataset separately. Given the representation provided by the diferent approaches, we used the Extra-Tree classifier [ 20]. As in the previous experiment, we decide the best model hyper-parameters by a combination of grid search and a 10-fold validation schema.
Figure 2 shows the accuracy (mean and standard deviation among the folds) result with diferent representation sizes: 2,10,20,50 and 100. Please note that the generated datasets are balanced, so mean accuracy among the fold and the standard deviation are accurate measurements. In Figure 2, we can observe that the SparseStruct is one of the best representation learning approaches in Brazilian and European air-trafic networks. While in the American air-trafic network, the SparseStruct clearly over-performs all the other approaches. In addition, in Figure 2, we can observe in SparseStruct has the desirable property that step by step, the representation size also increases the accuracy increases. This happens until, at a certain size, the performance is not going to change.
In this paper, we proposed SparseStruct, a large-scale sparse structural representation learning approach for graph nodes. SparseStruct theoretically and empirically preserves the graph structure of each node, and it has a execution time linear in the size of the graph. In our experiments, SparseStruct is often superior or comparable to current state-of-art representation learning approaches on both classification and regression tasks.
Future works is mainly oriented to embed novel features of big data within our framework (e.g., [21, 22]).
This work is partially supported by NSERC (Canada) and University of Manitoba. [5] L. F. Ribeiro, P. H. Saverese, D. R. Figueiredo, struc2vec: Learning node representations from structural identity, in: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2017, pp. 385–394. [6] C. Donnat, M. Zitnik, D. Hallac, J. Leskovec, Learning structural node embeddings via difusion wavelets, in: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, ACM, 2018, pp. 1320–1329. [7] D. Zhang, J. Yin, X. Zhu, C. Zhang, Network representation learning: A survey, IEEE transactions on Big Data (2018). [8] P. C. Hansen, The truncatedsvd as a method for regularization, BIT Numerical Mathematics 27 (1987) 534–553. [9] J. Shlens, A tutorial on principal component analysis, arXiv preprint arXiv:1404.1100 (2014). [10] P. D. Turney, Mining the web for synonyms: Pmi-ir versus lsa on toefl, in: European conference on machine learning, Springer, 2001, pp. 491–502. [11] A. C. Gilbert, J. Y. Park, M. B. Wakin, Sketched svd: Recovering spectral features from compressive measurements, arXiv preprint arXiv:1211.0361 (2012). [12] N. Halko, P.-G. Martinsson, J. A. Tropp, Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions (2009). [13] B. L. Douglas, The weisfeiler-lehman method and graph isomorphism testing, arXiv preprint arXiv:1101.5211 (2011). [14] A. Grover, J. Leskovec, node2vec: Scalable feature learning for networks, in: Proceedings of the 22nd ACM
SIGKDD international conference on Knowledge discovery and data mining, ACM, 2016, pp. 855–864. [15] W. Hamilton, Z. Ying, J. Leskovec, Inductive representation learning on large graphs, in: Advances in neural information processing systems, 2017, pp. 1024–1034. [16] S. Pan, R. Hu, G. Long, J. Jiang, L. Yao, C. Zhang, Adversarially regularized graph autoencoder for graph embedding, arXiv preprint arXiv:1802.04407 (2018). [17] K. Tu, P. Cui, X. Wang, P. S. Yu, W. Zhu, Deep recursive network embedding with regular equivalence, in: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 2357–2366. [18] J. Leskovec, A. Krevl, Snap datasets: Stanford large network dataset collection, 2014. [19] C. Cortes, V. Vapnik, Support-vector networks, Machine learning 20 (1995) 273–297. [20] P. Geurts, D. Ernst, L. Wehenkel, Extremely randomized trees, Machine learning 63 (2006) 3–42. [21] A. Cuzzocrea, W. Wang, Approximate range-sum query answering on data cubes with probabilistic guarantees,
J. Intell. Inf. Syst. 28 (2007) 161–197. [22] A. Cuzzocrea, Accuracy control in compressed multidimensional data cubes for quality of answer-based OLAP tools, in: 18th International Conference on Scientific and Statistical Database Management, SSDBM 2006, 3-5 July 2006, Vienna, Austria, Proceedings, IEEE Computer Society, 2006, pp. 301–310.