In recent years, graph neural networks (GNNs) have become a popular tool for solving various problems over graphs. In these models, the link structure of the graph is typically exploited and nodes’ embeddings are iteratively updated based on adjacent nodes. Nodes’ contents are used solely in the form of feature vectors, served as nodes’ first-layer embeddings. However, the filters or convolutions, applied during iterations/layers to these initial embeddings lead to their impact diminish and contribute insignificantly to the final embeddings. To address this issue, in this article we propose augmenting nodes’ embeddings by embeddings generated from their content, at higher GNN layers. More precisely, we propose models wherein a structural embedding using a GNN and a content embedding are computed for each node. These two are combined using a combination layer to form the embedding of a node at a given layer layer. We suggest methods such as using an auto-encoder or building a content graph to generate content embeddings. In the end, by conducting experiments over several real-world datasets, we demonstrate the high accuracy and performance of our models.

A well-studied problem in data mining is large itemset mining. To address this problem over very large datasets, several approximate algorithms have been introduced, where an important class of such methods relies on sampling. However in the literature, only methods that are based on uniform sampling are investigated. In this paper, first we discuss how different sampling methods can be described using a generic sampling algorithm and study a property desirable for sampling methods. Then we use this property to argue that some non-uniform sampling methods may work better. We accordingly propose methods that sample each transaction proportional to its number of items or proportional to its number of frequent items. Finally, by conducting extensive experiments over real-world datasets, we show that non-uniform sampling methods usually outperform the uniform method.

With the growing rate of online social networks, the number of fake accounts is multiplying day by day. There exist many approaches in the literature that try to distinguish fake accounts from real ones, for example, those that use machine learning and classification techniques to learn whether a user should be labeled as fake (bot) or not. In this paper, we follow a different approach and try to use node measurements in the field of complex networks analysis to identify fake accounts. We first model users’ interactions with a large graph. For example, in Twitter, we can form graphs of follower-following, comments, retweets, mentions, and so on. We then investigate different measurements, such as centrality indices and their correlations, to separate real and fake accounts. We find that measurements such as average path length, eigenvector centrality, harmonic centrality, degree, local reaching centrality and their correlations provide good indicators to distinguish real and fake accounts.

A technique that has recently become popular to analyze graph data is node embedding learning. Many graph problems, such as node classification, link prediction and node clustering, can be solved using these embeddings. However, in the literature the efficiency of different embedding generation algorithms paired with different clustering algorithms is not extensively investigated. In this paper, we study the efficiency of well-known embedding generation algorithms in combination with clustering algorithms, to detect communities. We consider four embedding generation algorithms that use mechanisms such as convolution, attention, inductivity and shallowness; and three popular data clustering algorithms. Our experimental results reveal that the combination of GraphSAGE (that uses inductivity) with KMeans++ yields the best results. This can be due to high quality of embedding vectors generated by GraphSAGE and the regular shapes that the embeddings find in the vector space.

In recent years, learning embeddings for nodes of a graph has become one of the most efficient w ays t o solve different graph problems such as link prediction, clustering and classification. I n t his p aper, w e p ropose a n ovel m ethod, called SECI, for learning embeddings of nodes, with application to link prediction. SECI samples from the network using breadth-first search and depth-first s earch, a nd i nterpolates b etween these two using centrality indices. The intuition behind SECI is that for nodes that have a low centrality score only a very small neighborhood is explored; and for dominant nodes that have a high centrality score a large neighborhood is explored. We evaluate the empirical performance of SECI over several realworld networks and show that it outperforms well-known existing algorithms.

A well-known problem in data science and machine learning is linear regression, which is recently extended to dynamic graphs. Existing exact algorithms for updating solutions of dynamic graph regression require at least a linear time (in terms of n: the number of nodes of the graph). However, this time complexity might be intractable in practice. In this paper, we utilize subsampled randomized Hadamard transform to propose a randomized algorithm for dynamic graphs. Suppose that we are given an nxm matrix embedding M of the graph, where m ⇐ n. Let r be the number of samples required for a guaranteed approximation error, which is a sublinear function of n. After an edge insertion or an edge deletion in the graph, our algorithm updates the approximate solution in O(rm) time.

Betweenness centrality and k-path centrality are two important indices that are widely used to analyze social, technological and information networks. In the current paper, first given a directed network G and a vertex $r\in V(G)$, we present a novel adaptive algorithm for estimating betweenness score of r. Our algorithm first computes two subsets of the vertex set of G, called $\mathcalRF (r)$ and $\mathcalRT (r)$. They define the sample spaces of the start-points and the end-points of the samples. Then, it adaptively samples from $\mathcalRF (r)$ and $\mathcalRT (r)$ and stops as soon as some condition is satisfied. The stopping condition depends on the samples met so far, $|\mathcalRF (r)|$ and $|\mathcalRT (r)|$. We show that compared to the well-known existing algorithms, our algorithm gives a better $(łambda,δ)$-approximation. Then, we propose a novel algorithm for estimating k-path centrality of r. Our algorithm is based on computing two sets $\mathcalRF (r)$ and $\mathcalD (r)$. While $\mathcalRF (r)$ defines the sample space of the source vertices of the sampled paths, $\mathcalD (r)$ defines the sample space of the other vertices of the paths. We show that in order to give a $(łambda,δ)$-approximation of the k-path score of r, our algorithm requires considerably less samples. Moreover, it processes each sample faster and with less memory. Finally, we empirically evaluate our proposed algorithms and show their superior performance. Also, we show that they can be used to efficiently compute centrality scores of a set of vertices.

One of the important indices defined for a set of vertices in a graph is group betweenness centrality. While in recent years a number of approximate algorithms have been proposed to estimate this index, there is no comprehensive and in-depth analysis and comparison of these algorithms in the literature. In this paper, we first present a generic algorithm that is used to express different approximate algorithms in terms of probability distributions. Using this generic algorithm, we show that interestingly existing methods have the same theoretical accuracy. Then, we present an extension of distance-based sampling to group betweenness centrality, which is based on a new notion of distance between a single vertex and a set of vertices. In the end, to empirically evaluate efficiency and accuracy of different algorithms, we perform experiments over several real-world networks. Our extensive experiments reveal that those approximate algorithms that are based on shortest path sampling are orders of magnitude faster than those algorithms that are based on pair sampling, while these two types of algorithms have almost comparable empirical accuracy.

An important index widely used to analyze social and information networks is betweenness centrality. In this paper, given a dynamic and directed graph G and a vertex r in G, we present the DyBED algorithm that updates the (approximate) betweenness centrality of r, when an update operation (vertex/edge insertion/deletion) occurs in G. Our algorithm first during pre-processing computes two subsets of the vertex set of G, called ΠT(r) and ΠT(r). The Cartesian product of these two sets defines the sample space of our algorithm. In other words, each sample is a pair, whose first element belongs to ΠT(r) and second element belongs to ΠT(r). Then after each update operation, DyBED updates the sets ΠT(r) and ΠT(r), the sampled pairs, the information stored for each sample and accordingly, the betweenness centrality of r. We theoretically and empirically evaluate DyBED and show that it yields significant improvement over existing work. In particular, our extensive experiments reveal that DyBED is orders of magnitude faster than most efficient existing algorithms.

Counting the number of triangles in a large graph has many important applications in network analysis. Several frequently computed metrics such as the clustering coefficient and the transitivity ratio need to count the number of triangles. In this paper, we present a randomized framework for expressing and analyzing approximate triangle counting algorithms. We show that many existing approximate triangle counting algorithms can be described in terms of probability distributions given as parameters to the proposed framework. Then, we show that our proposed framework provides a quantitative measure for the quality of different approximate algorithms. Finally, we perform experiments on real-world networks from different domains and show that there is no unique sampling technique outperforming the others for all networks and the quality of sampling techniques depends on different factors such as the structure of the network, the vertex degree-triangle correlation and the number of samples.

Betweenness centrality of vertices is essential in the analysis of social and information networks, and co-betweenness centrality is one of two natural ways to extend it to sets of vertices. Existing algorithms for co-betweenness centrality computation suffer from at least one of the following problems: i) their applicability is limited to special cases like sequences, sets of size two, and ii) they are not efficient in terms of time complexity. In this paper, we present efficient algorithms for co-betweenness centrality computation of any set or sequence of vertices in weighted and unweighted networks. We also develop effective methods for co-betweenness centrality computation of sets and sequences of edges. These results provide a clear and extensive view about the complexity of co-betweenness centrality computation for vertices and edges in weighted and un-weighted networks. Finally, we perform extensive experiments on real-world networks from different domains including social, information and communication networks, to show the empirical efficiency of the proposed methods.

Betweenness centrality is an important centrality measure widely used in social network analysis, route planning etc. However, even for mid-size networks, it is practically intractable to compute exact betweenness scores. In this paper, we propose a generic randomized framework for unbiased approximation of betweenness centrality. The proposed framework can be adapted with different sampling techniques and give diverse methods. We discuss the conditions a promising sampling technique should satisfy to minimize the approximation error and present a sampling method partially satisfying the conditions. We perform extensive experiments and show the high efficiency and accuracy of the proposed method.

Frequent tree patterns have many applications in different domains such as XML document mining, user web log analysis, network routing and bioinformatics. In this paper, we first introduce three new tree encodings and accordingly present an efficient algorithm for finding frequent patterns from rooted unordered trees with the assumption that children of every node in database trees are identically labeled. Then, we generalize the method and propose the UITree algorithm to find frequent patterns from rooted unordered trees without any restriction. Compared to other algorithms in the literature, UItree manages occurrences of a candidate tree in database trees more efficiently. Our extensive experiments on both real and synthetic datasets show that UITree significantly outperforms the most efficient existing works on mining unordered trees.

Mining frequent tree patterns has many practical applications in areas such as XML document mining, Web mining, bioinformatics, network routing and so on. Most of the previous works used an apriori-based approach for candidate generation and frequency counting in their algorithms. In these approaches the state space grows exponentially since many unreal candidates are generated, especially when there are lots of large patterns among the data. To tackle these problems, we propose TDU, a top-down approach for mining all maximal, labeled, unordered, and embedded subtrees from a collection of tree-structured data. We would evaluate the effectiveness of the TDU algorithm in comparison to the previous works

Tree structures have gained popularity for storing data from different domains such as XML documents, bio informatics and so on. Clustering these data can facilitate different operations. In this paper, we propose TreeCluster, a novel and heuristic algorithm for clustering tree structured data. This algorithm considers a representative tree for each cluster. For each input tree T, TreeCluster computes the composition of the tree T and each of the clusters. Tree T belongs to the cluster which its composed tree gains the best score. After adding a tree to a cluster the representative tree of that cluster is updated. We evaluate the accuracy of the TreeCluster algorithm in comparison to the previous works