Search

Social networks are crucial channels for information dissemination because they facilitate the effective exchange of ideas and information. The extensive utilization of these networks in daily life results in their explosive growth. Most methods are not practical for large-scale network analysis. Hence, analyzing a small portion instead of the whole network could be preferable, a technique known as graph sampling. According to a literature review, many approaches to graph sampling focus only on representing connectivity from triangle count assessment or node degree evaluation rather than both. This paper introduces an innovative method called TDGS (triangle-induced and degree-wise graph sampling) for producing a sample under the impact of both triangle count and node degree in social networks. The key idea behind TDGS is that it uses a centrality measure based on the degree centrality and local information of nodes about the connectivity of their neighbors to guide the sampling process. Furthermore, TDGS proposes a distributed model that can handle large-scale graphs. We evaluate the performance of our proposed method using real-world social networks. The experimental results show that TDGS provides significantly more precise information about node degrees than the well-known graph sampling methods and can estimate the global clustering coefficient with fewer estimation errors. [ABSTRACT FROM AUTHOR]

Bus passenger flow prediction is a crucial issue of public transportation planning and management. Though spatio-temporal graph convolution has shown promising results for subway passenger flow prediction, the existing spatial modeling methods based on graph convolution will bring huge spatial memory consumption for complex bus lines and larger-scale node data. Additionally, bus passenger flow is significantly influenced by immediate traffic conditions within a short time. To tackle these challenges, a multi-scale fusion and dynamic adaptive graph bus passenger flow prediction model (MFDAG) is presented. The proposed model effectively integrates passenger flow, time, and weekly information to enhance the feature dimension of the data. Moreover, it employs a dynamic adaptive graph method to learn the relationships between different stations. Furthermore, a multi-scale fusion propagation method is proposed to represent the complex spatial dependency relation, and a multi-scale convolution propagation method is designed to learn the multi-scale temporal dependency relation. The experiments are conducted by using two passenger flow datasets, and the results are compared with other traffic prediction methods. Experimental results demonstrate that the proposed bus passenger flow prediction method based on multi-scale fusion and dynamic adaptive graph exhibits higher prediction accuracy.

Abstract Graph sampling plays an important role in data mining for large networks. Specifically, larger networks often correspond to lower sampling rates. Under the situation, traditional traversal-based samplings for large networks usually have an excessive preference for densely-connected network core nodes. Aim at this issue, this paper proposes a sampling method for unknown networks at low sampling rates, called SLSR, which first adopts a random node sampling to evaluate a degree threshold, utilized to distinguish the core from periphery, and the average degree in unknown networks, and then runs a double-layer sampling strategy on the core and periphery. SLSR is simple that results in a high time efficiency, but experiments verify that the proposed method can accurately preserve many critical structures of unknown large scale-free networks with low sampling rates and low variances.

Copyright of Journal of Frontiers of Computer Science & Technology is the property of Beijing Journal of Computer Engineering & Applications Journal Co Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Social media embeddedness relationships consist of online social networks formed by self-organized individual actors and significantly affect many aspects of our lives. Since the high cost and inefficiency of using population networks generated by social media embeddedness relationships to study practical issues, sampling techniques have become increasingly important than ever. Our work consists of three parts. We first comprehensively analyze current sampling selection methods, evaluation indexes, and evaluation methods in terms of technological evolution. In the second part, we systematically conduct sampling tests using representative large-scale social media datasets. The test results indicate that unequal-probability sampling methods can construct similar sample networks at the macroscale and microscale and outperform the equal-probability methods. However, non-negligible sampling errors at the mesoscale seriously affect the sampling reliability and validity. MANOVA tests show that the direct cause of sampling errors is the low in-degree nodes with medium-high betweenness located between the core and periphery, and current sampling methods cannot accurately sample such complex interconnected structures. In the third part, we summarize the pros and cons of current sampling methods and provide suggestions for future work. [ABSTRACT FROM AUTHOR]

Orthogonal frequency division multiplexing (OFDM) is one of the key technologies in the physical layer of the internet of things (IoT).Pilot design and channel estimation are key issues in OFDM systems.In view of the problem of performance loss by fixed pilot pattern due to the complexity and variety of IoT communication scenarios, a pilot design and channel estimation scheme based on graph signal processing (GSP) was proposed.Firstly, the time-frequency resource block was modeled as a graph signal, and the channel estimation problem was reformulated into a sampling and reconstruction problem of the graph signal.Then, considering the influence of time-frequency fading, a weighted graph adjacency matrix was designed to construct a graph topology structure based on the time-frequency position.On this basis, the pilot position is selected based on the graph signal sampling theory, a greedy pilot pattern design algorithm based on weighted graph topology was proposed.At the same time, signal reconstruction was performed based on the graph signal reconstruction method, and a channel estimation method based on the graph smoothness constraint was proposed.Compared with the conventional scheme, simulation results show that the proposed method achieves higher channel estimation accuracy in high-speed scenarios of double selective channels, and effectively reduces pilot overhead in low-speed scenarios.

Federated learning has attracted much research attention due to its privacy protection in distributed machine learning. However, existing work of federated learning mainly focuses on Convolutional Neural Network (CNN), which cannot efficiently handle graph data that are popular in many applications. Graph Convolutional Network (GCN) has been proposed as one of the most promising techniques for graph learning, but its federated setting has been seldom explored. In this article, we propose FedGraph for federated graph learning among multiple computing clients, each of which holds a subgraph. FedGraph provides strong graph learning capability across clients by addressing two unique challenges. First, traditional GCN training needs feature data sharing among clients, leading to risk of privacy leakage. FedGraph solves this issue using a novel cross-client convolution operation. The second challenge is high GCN training overhead incurred by large graph size. We propose an intelligent graph sampling algorithm based on deep reinforcement learning, which can automatically converge to the optimal sampling policies that balance training speed and accuracy. We implement FedGraph based on PyTorch and deploy it on a testbed for performance evaluation. The experimental results of four popular datasets demonstrate that FedGraph significantly outperforms existing work by enabling faster convergence to higher accuracy. [ABSTRACT FROM AUTHOR]

Abstract Graph sampling methods have been used to reduce the size and complexity of big complex networks for graph mining and visualization. However, existing graph sampling methods often fail to preserve the connectivity and important structures of the original graph. This paper introduces a new divide and conquer approach to spectral graph sampling based on graph connectivity, called the BC Tree (i.e., decomposition of a connected graph into biconnected components) and spectral sparsification. Specifically, we present two methods, spectral vertex sampling $$BC\_SV$$ B C _ S V and spectral edge sampling $$BC\_SS$$ B C _ S S by computing effective resistance values of vertices and edges for each connected component. Furthermore, we present $$DBC\_SS$$ D B C _ S S and $$DBC\_GD$$ D B C _ G D , graph connectivity-based distributed algorithms for spectral sparsification and graph drawing respectively, aiming to further improve the runtime efficiency of spectral sparsification and graph drawing by integrating connectivity-based graph decomposition and distributed computing. Experimental results demonstrate that $$BC\_SV$$ B C _ S V and $$BC\_SS$$ B C _ S S are significantly faster than previous spectral graph sampling methods while preserving the same sampling quality. $$DBC\_SS$$ D B C _ S S and $$DBC\_GD$$ D B C _ G D obtain further significant runtime improvement over sequential approaches, and $$DBC\_GD$$ D B C _ G D further achieves significant improvements in quality metrics over sequential graph drawing layouts.

It is very significant to learn graph representation by using only the network topology information in many application scenarios, where attributes of nodes are not available or not easy to obtain. Although existing approaches have achieved impressive performance, they cannot deterministically involve important nodes related to the current node in the representation learning process, leading to a lack of robustness. To address this problem, we propose a novel symmetric cumulative sampling strategy for unsupervised graph representation learning via multi-step propagation and aggregation sampling, named MPMA. According to generated hierarchical transition probabilities, MPMA is able to select crucial nodes and construct pyramidal node subsets from both propagation and aggregation perspectives. Based on the constructed node subsets, an efficient algorithm is employed to search the shortest paths between the current node and each important node to preserve sufficient interaction of nodes. Extensive experiments on diverse application tasks verify the effectiveness and robustness of the proposed method. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Zhejiang University (Science Edition) is the property of Journal of Zhejiang University (Science Edition) Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Background It is often the case that only a portion of the underlying network structure is observed in real-world settings. However, as most network analysis methods are built on a complete network structure, the natural questions to ask are: (a) how well these methods perform with incomplete network structure, (b) which structural observation and network analysis method to choose for a specific task, and (c) is it beneficial to complete the missing structure. Methods In this paper, we consider the incomplete network structure as one random sampling instance from a complete graph, and we choose graph neural networks (GNNs), which have achieved promising results on various graph learning tasks, as the representative of network analysis methods. To identify the robustness of GNNs under graph sampling scenarios, we systemically evaluated six state-of-the-art GNNs under four commonly used graph sampling methods. Results We show that GNNs can still be applied on single static networks under graph sampling scenarios, and simpler GNN models are able to outperform more sophisticated ones in a fairly experimental procedure. More importantly, we find that completing the sampled subgraph does improve the performance of downstream tasks in most cases; however, completion is not always effective and needs to be evaluated for a specific dataset. Our code is available at https://github.com/weiqianglg/evaluate-GNNs-under-graph-sampling.

Accurate identification of the miRNA-disease associations (MDAs) helps to understand the etiology and mechanisms of various diseases. However, the experimental methods are costly and time-consuming. Thus, it is urgent to develop computational methods towards the prediction of MDAs. Based on the graph theory, the MDA prediction is regarded as a node classification task in the present study. To solve this task, we propose a novel method MDA-GCNFTG, which predicts MDAs based on Graph Convolutional Networks (GCNs) via graph sampling through the Feature and Topology Graph to improve the training efficiency and accuracy. This method models both the potential connections of feature space and the structural relationships of MDA data. The nodes of the graphs are represented by the disease semantic similarity, miRNA functional similarity and Gaussian interaction profile kernel similarity. Moreover, we considered six tasks simultaneously on the MDA prediction problem at the first time, which ensure that under both balanced and unbalanced sample distribution, MDA-GCNFTG can predict not only new MDAs but also new diseases without known related miRNAs and new miRNAs without known related diseases. The results of 5-fold cross-validation show that the MDA-GCNFTG method has achieved satisfactory performance on all six tasks and is significantly superior to the classic machine learning methods and the state-of-the-art MDA prediction methods. Moreover, the effectiveness of GCNs via the graph sampling strategy and the feature and topology graph in MDA-GCNFTG has also been demonstrated. More importantly, case studies for two diseases and three miRNAs are conducted and achieved satisfactory performance. [ABSTRACT FROM AUTHOR]

In recent years, deep learning has drawn increasing attention in the field of hyperspectral remote sensing image classification and has achieved great success. However, the traditional convolutional neural network model has a huge parameter space, in order to obtain a better classification model, a large number of labeled samples are often required. In this paper, a graph induction learning method is proposed to solve the problem of small sample in hyperspectral image classification. It treats each pixel of the hyperspectral image as a graph node and learns the aggregation function of adjacent vertices through graph sampling and graph aggregation operations to generate the embedding vector of the target vertex. Experimental results on three well-known hyperspectral data sets show that this method is superior to the current semi-supervised methods and advanced deep learning methods.

Abstract Many networks including spatial networks, social networks, and web networks, are not deterministic but probabilistic due to the uncertainty of link existence. From networks with such uncertainty, to extract densely connected nodes, we propose connectedness centrality and its extended version, group connectedness centrality, where the connectedness of each node is defined as the expected size of its connected component over all possible graphs produced by an uncertain graph. In a large-scale network, however, since the number of combinations of possible graphs is enormous, it is difficult to strictly calculate the expected value. Therefore, we also propose an efficient estimation method based on Monte Carlo sampling. When applying our method to road networks, the extracted nodes can be regarded as candidate sites of evacuation facilities that many residents can reach even in the situation where roads are stochastically blocked by natural disasters. In our experimental evaluations using actual road networks, we show the following promising characteristics: our proposed method 1) works stably with respect to the number of simulations; 2) extracts nodes set reachable from more nodes even in a situation that many links are deleted; and 3) computes much more efficient, compared to existing centrality measures and community extraction methods.

This paper deals with randomized polling of a social network. In the case of forecasting the outcome of an election between two candidates A and B, classical intent polling asks randomly sampled individuals: who will you vote for? Expectation polling asks: who do you think will win? In this paper, we propose a novel neighborhood expectation polling (NEP) strategy that asks randomly sampled individuals: what is your estimate of the fraction of votes for A? Therefore, in NEP, sampled individuals will naturally look at their neighbors (defined by the underlying social network graph) when answering this question. Hence, the mean squared error (MSE) of NEP methods rely on selecting the optimal set of samples from the network. To this end, we propose two NEP algorithms for the following cases: (i) the social network graph is not known but, random walks (sequential exploration) can be performed on the graph, and (ii) the social network graph is unknown but, uniformly sampled nodes from the network are available. For both cases, algorithms based on a graph theoretic consequence called friendship paradox are proposed. Theoretical results on the dependence of the MSE of the algorithms on the properties of the network are established. Numerical results on real and synthetic data sets are provided to illustrate the performance of the algorithms. [ABSTRACT FROM AUTHOR]

Graph Neural Networks (GNNs) are powerful deep learning models to generate node embeddings on graphs. When applying deep GNNs on large graphs, it is still challenging to perform training in an efficient and scalable way. We propose a novel parallel training framework. Through sampling small subgraphs as minibatches, we reduce training workload by orders of magnitude compared with state-of-the-art minibatch methods. We then parallelize the key computation steps on tightly-coupled shared memory systems. For graph sampling, we exploit parallelism within and across sampler instances, and propose an efficient data structure supporting concurrent accesses from samplers. The parallel sampler theoretically achieves near-linear speedup with respect to number of processing units. For feature propagation within subgraphs, we improve cache utilization and reduce DRAM traffic by data partitioning. Our partitioning is a 2-approximation strategy for minimizing the communication cost compared to the optimal. We further develop a runtime scheduler to reorder the training operations and adjust the minibatch subgraphs to improve parallel performance. Finally, we generalize the above parallelization strategies to support multiple types of GNN models and graph samplers. The proposed training outperforms the state-of-the-art in scalability, efficiency and accuracy simultaneously. On a 40-core Xeon platform, we achieve 60 × speedup (with AVX) in the sampling step and 20 × speedup in the feature propagation step, compared to the serial implementation. Our algorithm enables fast training of deeper GNNs, as demonstrated by orders of magnitude speedup compared to the Tensorflow implementation. We open-source our code at https://github.com/GraphSAINT/GraphSAINT • Novel minibatch algorithm for training graph convolutional networks. • Parallel algorithm to scale graph representation learning. • Theoretical performance guarantee for parallel execution of the training algorithm. • Intelligent graph partitioning for optimal memory performance and load-balance. [ABSTRACT FROM AUTHOR]

The Discrete Pulse Transform (DPT) makes use of LULU smoothing to decompose a signal into block pulses. The most recent and effective implementation of the DPT is an algorithm called the Roadmaker's Pavage, which uses a graph-based algorithm that produces a hierarchical tree of pulses as its final output, shown to have important applications in artificial intelligence and pattern recognition. Even though the Roadmaker's Pavage is an efficient implementation, the theoretical structure of the DPT results in a slow, deterministic algorithm. This paper examines the use of the spectral domain of graphs and designing graph filter banks to downsample the algorithm. We investigate the extent to which this speeds up the algorithm and allows parallel processing. Converting graph signals to the spectral domain can also be a costly overhead, so methods of estimation for filter banks are examined, as well as the design of a good filter bank that may be reused without needing recalculation. The sampled version requires different hyperparameters in order to reconstruct the same textures of the image as the original algorithm, selected previously either through trial and error (subjective) or grid search (costly) which prevented studying the results on many images effectively. Here an objective and efficient way of deriving similar results between the original Roadmaker's Pavage and our proposed Filtered Roadmaker's Pavage is provided. The method makes use of the Ht-index which separates the distribution of information in the graph at scale intervals by recursively calculating averages on decreasing subsections of the scale data stored. This has enabled empirical research using benchmark datasets providing improved results. The results of these empirical tests showed that using the Filtered Roadmaker's Pavage algorithm consistently runs faster, using less computational resources, while having a positive SSIM (structural similarity) with low variance. This provides an informative and faster approximation to the nonlinear DPT, a property which is not standardly achieveable. [ABSTRACT FROM AUTHOR]

An increasing number of networks are becoming large-scale and continuously growing in nature, such that clustering on them in their entirety could be intractable. A feasible way to overcome this problem is to sample a representative subgraph and exploit its clustering structure (namely, sample clustering process). However, there are two issues that we should address in current studies. One underlying question is how to evaluate the clustering quality of the entire sample clustering process. Another non-trivial issue is that multiple ground-truths exist in networks, thus evaluating the clustering results in such scenario is also a challenging task. In this paper, first we utilize the set-matching methodology to quantitatively evaluate how differently the clusters of the sampled counterpart correspond to the ground-truth(s) in the original graph, and propose several new quality metrics to capture the differences of clustering structure in various aspects. Second, we put forward an evaluation framework for the general problems of evaluating the clustering quality on graph samples. Extensive experiments on various synthetic and real-world graphs demonstrate that our new quality metrics are more accurate and insightful for the sample clustering evaluation than conventional metrics (e.g., NMI). Thus the evaluation framework is effective and practical to assess the clustering quality of the sample clustering process on massive graphs. [ABSTRACT FROM AUTHOR]

Large real-world graphs claim lots of resources in terms of memory and computational power to study them and this makes their full analysis extremely challenging. In order to understand the structure and properties of these graphs, we intend to extract a small representative subgraph from a big graph while preserving its topology and characteristics. In this work, we aim at producing good samples with sample size as low as 0.1% while maintaining the structure and some of the key properties of a network. We exploit the fact that average values of degree and clustering coefficient of a graph can be estimated accurately and efficiently. We use the estimated values to guide the sampling process and extract tiny samples that preserve the properties of the graph and closely approximate their distributions in the original graph. The distinguishing feature of our work is that we apply traversal based sampling that utilizes only the local information of nodes as opposed to the global information of the network and this makes our approach a practical choice for crawling online networks. We evaluate the effectiveness of our sampling technique using real-world datasets and show that it surpasses the existing methods. [ABSTRACT FROM AUTHOR]

Frequent pattern mining (FPM), whose goal is to identify patterns with appearance frequencies above a specified support threshold on a large graph, has attracted increasing attention owing to its diverse applications. The task suffers from an issue of support setting, as an inappropriate support threshold may lead to either extremely high computational cost along with a huge pattern set or very few patterns caused by excessive pruning. Thus, supports estimation is crucial for FPM, since an appropriate support threshold enables users to discover a limited number of patterns within affordable computational resources. In light of this, we investigate the problem of supports estimation under the constraint of pattern number B and propose a comprehensive approach to the issue. Our approach leverages a neural network to predict the support θ B that corresponds to the B -th pattern on a graph G. To train the prediction model, we first present a sampling algorithm that leverages typical motifs to produce sampled graphs of G under different sampling ratios. Owing to the typical structures brought about by motifs, the sampled graphs are embedded supports of the top-ranked patterns in proportion to the sampling ratios. We next develop techniques to efficiently infer the support θ B of the B -th pattern on each sampled graph and introduce a method to encode (sampled) graphs with θ B and other typical features, thereby forming the training data. Extensive experimental studies on real-life and synthetic graphs demonstrate the superiority of our approach, compared to other baselines. • We introduce a motifs-based graph sampling algorithm that reserves salient features. • We develop a support-threshold-free mining algorithm to identify top-B patterns. • We built a neural network model to perform support estimation. [ABSTRACT FROM AUTHOR]

Dynamic network visualization is crucial to understand network evolving behavior. Massive sequence view (MSV) is a classic technique for visualizing dynamic networks and provides users with a fine-grained presentation of time-varying communication trend from both node pair and global network levels. However, MSV is vulnerable to visual clutter caused by overlapping edges, failing to show clear patterns or trends. This paper presents an edge sampling method, using the edge overlapping degree (EOD) concept, to reduce visual clutter in MSV while preserving the time-varying features of network communication. Referring to accept-reject sampling, we use kernel density estimation to characterize the time-varying features between node pairs and generate EOD probability density functions to accomplish sampling in a bottom-up manner. To enhance the sampling effect, we also consider the edge length factor and streaming processing. The case studies on two dynamic network data sets demonstrate that our method can significantly improve the overall readability of MSV and clearly reveal the temporal features of both node pairs and global network. A quantitative evaluation comparing with two other sampling methods using three real-world data sets indicates that our method can well balance visual clutter reduction and temporal feature preservation.

Random walk-based sampling methods are gaining popularity and importance in characterizing large networks. While powerful, they suffer from the slow mixing problem when the graph is loosely connected, which results in poor estimation accuracy. Random walk with jumps (RWwJ) can address the slow mixing problem but it is inapplicable if the graph does not support uniform vertex sampling (UNI). In this work, we develop methods that can efficiently sample a graph without the necessity of UNI but still enjoy the similar benefits as RWwJ. We observe that many graphs under study, called target graphs, do not exist in isolation. In many situations, a target graph is related to an auxiliary graph and a bipartite graph, and they together form a better connected two-layered network structure. This new viewpoint brings extra benefits to graph sampling: if directly sampling a target graph is difficult, we can sample it indirectly with the assistance of the other two graphs. We propose a series of new graph sampling techniques by exploiting such a two-layered network structure to estimate target graph characteristics. Experiments conducted on both synthetic and real-world networks demonstrate the effectiveness and usefulness of these new techniques. [ABSTRACT FROM AUTHOR]

Counting the number of times a pattern occurs in a database is a fundamental data mining problem. It is a subroutine in a diverse set of tasks ranging from pattern mining to supervised learning and probabilistic model learning. While a pattern and a database can take many forms, this paper focuses on the case where both the pattern and the database are graphs (networks). Unfortunately, in general, the problem of counting graph occurrences is #P-complete. In contrast to earlier work, which focused on exact counting for simple (i.e., very short) patterns, we present a sampling approach for estimating the statistics of larger graph pattern occurrences. We perform an empirical evaluation on synthetic and real-world data that validates the proposed algorithm, illustrates its practical behavior and provides insight into the trade-off between its accuracy of estimation and computational efficiency. [ABSTRACT FROM AUTHOR]

In this article, we propose a general model of data collection from social media, in the context of terrorism research, focusing on recent studies of jihadists. By analyzing Twitter data collection methods in the existing research, we show that the methods used are prone to sampling biases, and that the sampled datasets are not sufficiently filtered or validated to ensure reliability of conclusions derived from them. Alternatively, we propose some best practices for the collection of data in future research on jihadist using social media (as well as other kinds of terrorist groups). Given the similarity of the methodological challenges posed by research on almost all social media platforms, in the context of terrorism studies, the critique and recommendations offered remain relevant despite the recent shift of most jihadists from Twitter to Telegram and other forms of social media. [ABSTRACT FROM AUTHOR]

Discriminative systems that can deal with graphs in input are known, however, generative or constructive approaches that can sample graphs from empirical distributions are less developed. Here we propose a Metropolis–Hastings approach that uses a novel type of graph grammar to efficiently learn proposal distributions in a data driven fashion. We report experimental results in a de-novo molecular synthesis problem where we show that the distribution of the molecules generated by the sampling procedure is accurate enough to improve a predictor's performance in a classification task. [ABSTRACT FROM AUTHOR]