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]

We develop lagged Metropolis–Hastings walk for sampling from simple undirected graphs according to given stationary sampling probabilities. It is explained how the technique can be applied together with designed graphs for sampling of units‐in‐space. Compared with the existing spatial sampling methods, which chiefly focus on the sample spatial balance regardless of the associated outcomes of interest, the proposed graph spatial sampling method can considerably improve the efficiency because the graph can be designed to take into account the anticipated spatial distribution of the outcome of interest. [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.)

The huge amount of graph data necessitates sampling methods to support graph-based analysis applications. Node influence is to count the influential nodes with a given node in large graphs that has wide applications including product promotion and information diffusion in social networks. However, existing sampling methods mainly consider node degree to compute the node influence while ignoring the important connections in terms of groups in which nodes participate, resulting in inaccuracy of influence estimations. To this end, this paper proposes group sampling, called GVRW, to count the groups along with node degrees to evaluate node influence in large graphs. Specifically, GVRW changes the way of random walker traversing a large graph from one node to a random neighbor node of the groups to enlarge the sampling space for the sake of characterizing the nodes and groups simultaneously. Furthermore, we carefully design the corresponding estimated method to employ the samples to estimate the specific distributions of groups and node degrees to compute the node influence. Experimental results on real-world graph datasets show that our proposed sampling and estimating methods can accurately obtain the properties and approximate the node influences closer to the real values than existing methods. [ABSTRACT FROM AUTHOR]

We show that the eigenpolytopes of graphs are universal in the sense that every polytope, up to affine equivalence, appears as the eigenpolytope of some positively weighted graph. We next extend the theory of graphical designs, which are quadrature rules for graphs, to positively weighted graphs. Through Gale duality for polytopes, we show a bijection between graphical designs and the faces of eigenpolytopes. This bijection proves the existence of graphical designs with positive quadrature weights and upper bounds the size of a minimal graphical design. Connecting this bijection with the universality of eigenpolytopes, we establish three complexity results: It is strongly NP-complete to determine if there is a graphical design smaller than the mentioned upper bound, it is NP-hard to find a smallest graphical design, and it is \#P-complete to count the number of minimal graphical designs. [ABSTRACT FROM AUTHOR]

In large-scale data processing, graph analytics of complex interaction networks are indispensable. As the whole graph processing and analytics can be inefficient and usually impractical, graph sampling by keeping a portion of the original graph becomes a favorable approach. While prior work focused on fixed edge and node selection strategy based on predetermined criteria, without adaptive feedback to adjust the sampling process, this type of sampling algorithms has limited flexibility and estimation accuracy for complex graphs. In this paper, we propose an adaptive graph sampling framework, and design AdapES, an adaptive edge sampling algorithm based on this framework. Compared to non-adaptive sampling methods, our approach can continually monitor the difference between the current sampled subgraph and the original graph, and dynamically adjust the edge sampling probability based on this observed sampling difference. Guided by a preset sampling goal, this algorithm automatically adapts to the fluctuations in the random sampling process with high flexibility. The experimental evaluation in 11 datasets demonstrates that AdapES outperforms other algorithms for preserving various graph properties and statistics. [ABSTRACT FROM AUTHOR]

We study graph sampling methods that seek to reconstruct original graph signals from sampled signals. Greedy approach that previous methods typically adopt computes the cost function (e.g., reconstruction error) for all remaining nodes at each step to find the node that minimizes the cost function. Noting that this computation causes a huge cost, we propose a low-complexity sampling process which computes the cost function for the nodes in a limited search range which is constructed by collecting the nodes with low values of the cost function since those are likely to be selected at the next step. Further, to achieve a complexity reduction for the proposed method, the search range is updated in the fixed interval which is experimentally determined in order to maintain reconstruction performance. We investigate the performance of the proposed algorithm in comparison with the previous methods for various graphs, demonstrating about 1.5 times faster execution time without degradation of reconstruction performance. [ABSTRACT FROM AUTHOR]

A graphical design is a subset of graph vertices such that the weighted averages of certain graph eigenvectors over the design agree with their global averages. We use Gale duality to show that positively weighted graphical designs in regular graphs are in bijection with the faces of a generalized eigenpolytope of the graph. This connection can be used to organize, compute and optimize designs. We illustrate the power of this tool on three families of Cayley graphs – cocktail party graphs, cycles, and graphs of hypercubes – by computing or bounding the smallest designs that average all but the last eigenspace in frequency order. [ABSTRACT FROM AUTHOR]

Bipartite incidence graph sampling provides a unified representation of many sampling situations for the purpose of estimation, including the existing unconventional sampling methods, such as indirect, network or adaptive cluster sampling, which are not originally described as graph problems. We develop a large class of design-based linear estimators, defined for the sample edges and subjected to a general condition of design unbiasedness. The class contains as special cases the classic Horvitz-Thompson estimator, as well as the other unbiased estimators in the literature of unconventional sampling, which can be traced back to Birnbaum et al. (1965). Our generalisation allows one to devise other unbiased estimators in future, thereby providing a potential of efficiency gains. Illustrations are given for adaptive cluster sampling, line-intercept sampling and simulated graphs. [ABSTRACT FROM AUTHOR]

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]

Copyright of Journal of Computer Engineering & Applications 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.)

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.

Graph sampling allows mining a small representative subgraph from a big graph. Sampling algorithms deploy different strategies to replicate the properties of a given graph in the sampled graph. In this study, we provide a comprehensive empirical characterization of five graph sampling algorithms on six properties of a graph including degree, clustering coefficient, path length, global clustering coefficient, assortativity, and modularity. We extract samples from fifteen graphs grouped into five categories including collaboration, social, citation, technological, and synthetic graphs. We provide both qualitative and quantitative results. We find that there is no single method that extracts true samples from a given graph with respect to the properties tested in this work. Our results show that the sampling algorithm that aggressively explores the neighborhood of a sampled node performs better than the others. [ABSTRACT FROM AUTHOR]

The prevalence of multi-dimensional (m-D) graph signals in various real-world applications, such as digital images and data with spatial and temporal dimensions, highlights their significance. However, efficiently sampling and reconstructing these m-D graph signals remains a significant challenge in the field of graph signal processing. In this paper, we study the generalized sampling framework of m-D graph signals based on prior knowledge. First, we consider the subspace priors of m-D graph signals, assuming that the signals are located in the periodic m-D graph spectral subspace. We design the reconstruction scheme through the subspace prior information. Then, we propose a generalized sampling framework for m-D graph signals based on smoothness prior information with lower constraints. It is still possible to recover the original m-D graph signal when the space where the m-D graph signal is located is unknown. In the above framework, sampling and reconstruction can be implemented efficiently, and there is no bandwidth limitation for the m-D graph signals. Finally, several experiments are performed to numerically validate the effectiveness of the proposed sampling framework. • We develop a sampling framework for m-D graph signals based on a subspace prior. • When the space is unknown, the original m-D graph signal can be reconstructed. • Our m-D graph signal sampling method is scalable. [ABSTRACT FROM AUTHOR]

Graph sampling is a very effective method to deal with scalability issues when analyzing large-scale graphs. Lots of sampling algorithms have been proposed, and sampling qualities have been quantified using explicit properties (e.g., degree distribution) of the sample. However, the existing sampling techniques are inadequate for the current sampling task: sampling the clustering structure, which is a crucial property of the current networks. In this paper, using different expansion strategies, two novel top-leader sampling methods (i.e., TLS-e and TLS-i) are proposed to obtain representative samples, and they are capable of effectively preserving the clustering structure. The rationale behind them is to select top-leader nodes of most clusters into the sample and then heuristically incorporate peripheral nodes into the sample using specific expansion strategies. Extensive experiments are conducted to investigate how well sampling techniques preserve the clustering structure of graphs. Our empirical results show that the proposed sampling algorithms can preserve the population’s clustering structure well and provide feasible solutions to sample the clustering structure from large-scale graphs. [ABSTRACT FROM AUTHOR]

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.

The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. In this work we study the problem of uniformly sampling graphs for which, in addition to the degree sequence, joint degree constraints are given. These constraints specify how many edges there should be between two given degree classes (i.e., subsets of nodes that all have the same degree). Although the problem was formalized over a decade ago, and despite its practical significance in generating synthetic network topologies, small progress has been made on the random sampling of such graphs. In the case of one degree class, the problem reduces to the sampling of regular graphs (i.e., graphs in which all nodes have the same degree), but beyond this very little is known. We fully resolve the case of two degree classes, by showing that the switch Markov chain is always rapidly mixing. We do this by combining a recent embedding argument developed by the authors in combination with ideas of Bhatnagar et al. [Algorithmica, 50 (2008), pp. 418--445] introduced in the context of sampling bichromatic matchings. [ABSTRACT FROM AUTHOR]

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]

Graphical designs are an extension of spherical designs to functions on graphs. We connect linear codes to graphical designs on cube graphs, and show that the Hamming code in particular is a highly effective graphical design. We show that even in highly structured graphs, graphical designs are distinct from the related concepts of extremal designs, maximum stable sets in distance graphs, and t-designs on association schemes. [ABSTRACT FROM AUTHOR]

Graphlets are induced subgraph patterns that are crucial to the understanding of the structure and function of a large network. A lot of effort has been devoted to calculating graphlet statistics where random walk-based approaches are commonly used to access restricted graphs through the available application programming interfaces (APIs). However, most of them merely consider individual networks while overlooking the strong coupling between different networks. In this article, we estimate the graphlet concentration in multiplex networks with real-world applications. An inter-layer edge connects two nodes in different layers if they actually belong to the same node. The access to a multiplex network is restrictive in the sense that the upper layer allows random walk sampling, whereas the nodes of lower layers can be accessed only through the interlayer edges and only support random node or edge sampling. To cope with this new challenge, we define a suit of two-layer graphlets and propose novel random walk sampling algorithms to estimate the proportion of all the three-node graphlets. An analytical bound on the sampling steps is proved to guarantee the convergence of our unbiased estimator. We further generalize our algorithm to explore the tradeoff between the estimated accuracy of different graphlets when the sample budget is split into different layers. Experimental evaluation on real-world and synthetic multiplex networks demonstrates the accuracy and high efficiency of our unbiased estimators. [ABSTRACT FROM AUTHOR]

Graph sampling is a challenging problem in network analysis due to the complex structures of networks. Currently, a series of graph sampling algorithms based on random walks achieve good results in graph sampling tasks. However, the existing methods often reduce the conductance of graphs, causing the sampler to stay in the same node for a long time. This results in undersampling. In this paper, we propose a novel Weighted Jump Random Walk (WJRW) algorithm to generate representative samples. We design a parameter in the WJRW algorithm that can adjust the proportions of random walk and random jump in every step. According to the issue of repeated sample nodes in the Generalized Maximum Degree (GMD) method and the problem of large deviations in the Simple Random Walk (SRW), WJRW addresses the weaknesses of the GMD method and enhances the diffusion of a random walker on graphs, leading to a more representative sample. Then, WJRW addresses the issue of large deviations in SRW and enhances the efficiency of the unbiased estimator. By generating smoother stationary distributions. Numerical experiments with extensive real-world networks verify that our method achieves higher accuracy than classical and state-of-the-art methods in estimating distribution estimation. [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.

Katz centrality is a fundamental concept to measure the influence of a vertex in a social network. However, existing approaches to calculating Katz centrality in a large-scale network are unpractical and computationally expensive. In this article, we propose a novel method to estimate Katz centrality based on graph sampling techniques, which object to achieve comparable estimation accuracy of the state-of-the-arts with much lower computational complexity. Specifically, we develop a Horvitz-Thompson estimate for Katz centrality by using a multi-round sampling approach and deriving an unbiased mean value estimator. We further propose SAKE, a Sampling-based Algorithm for fast Katz centrality Estimation. We prove that the estimator calculated by SAKE is probabilistically guaranteed to be within an additive error from the exact value. Extensive evaluation experiments based on four real-world networks show that the proposed algorithm can estimate Katz centralities for partial vertices with low sampling rate, low computation time, and it works well in identifying high influence vertices in social networks. [ABSTRACT FROM AUTHOR]

In everyday life, we often observe unusually frequent interactions among people before or during important events, e.g., people send/receive more greetings to/from their friends on holidays than regular days. We also observe that some videos or hashtags suddenly go viral through people's sharing on online social networks (OSNs). Do these seemingly different phenomena share a common structure? All these phenomena are associated with the sudden surges of node interactions in networks, which we call "bursts" in this work. We uncover that, in many scenarios, the emergence of a burst is accompanied with the formation of triangles in networks. This finding motivates us to propose a new and robust method for burst detection on an OSN. We first introduce a new measure, i.e., "triadic cardinality distribution," corresponding to the fractions of nodes with different numbers of triangles, i.e., triadic cardinalities, in a network. We show that this distribution not only changes when a burst occurs, but it also has a robustness property that it is immunized against common spamming social-bot attacks. Hence, by tracking triadic cardinality distributions, we can more reliably detect bursts than simply counting node interactions on an OSN. To avoid handling massive activity data generated by OSN users during the triadic tracking, we design an efficient "sample-estimate" framework to provide maximum likelihood estimate of the triadic cardinality distribution. We propose several sampling methods and provide insights into their performance difference through both theoretical analysis and empirical experiments on real-world networks. [ABSTRACT FROM AUTHOR]

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]

Numerous sampling strategies have been proposed to simplify large-scale networks for highly readable visualizations. It is of great challenge to preserve contextual structures formed by nodes and edges with tight relationships in a sampled graph, because they are easily overlooked during the process of sampling due to their irregular distribution and immunity to scale. In this paper, a new graph sampling method is proposed oriented to the preservation of contextual structures. We first utilize a graph representation learning (GRL) model to transform nodes into vectors so that the contextual structures in a network can be effectively extracted and organized. Then, we propose a multi-objective blue noise sampling model to select a subset of nodes in the vectorized space to preserve contextual structures with the retention of relative data and cluster densities in addition to those features of significance, such as bridging nodes and graph connections. We also design a set of visual interfaces enabling users to interactively conduct context-aware sampling, visually compare results with various sampling strategies, and deeply explore large networks. Case studies and quantitative comparisons based on real-world datasets have demonstrated the effectiveness of our method in the abstraction and exploration of large networks. [ABSTRACT FROM AUTHOR]

Sampling is a widely used graph reduction technique to accelerate graph computations and simplify graph visualizations. By comprehensively analyzing the literature on graph sampling, we assume that existing algorithms cannot effectively preserve minority structures that are rare and small in a graph but are very important in graph analysis. In this work, we initially conduct a pilot user study to investigate representative minority structures that are most appealing to human viewers. We then perform an experimental study to evaluate the performance of existing graph sampling algorithms regarding minority structure preservation. Results confirm our assumption and suggest key points for designing a new graph sampling approach named mino-centric graph sampling (MCGS). In this approach, a triangle-based algorithm and a cut-point-based algorithm are proposed to efficiently identify minority structures. A set of importance assessment criteria are designed to guide the preservation of important minority structures. Three optimization objectives are introduced into a greedy strategy to balance the preservation between minority and majority structures and suppress the generation of new minority structures. A series of experiments and case studies are conducted to evaluate the effectiveness of the proposed MCGS. [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]