Fine-Grained Sketch-Based Image Retrieval (FG-SBIR) aims to minimize the distance between sketches and corresponding images in the embedding space. However, scalability is hindered by the growing complexity of solutions, mainly due to the abstract nature of fine-grained sketches. In this paper, we propose an effective approach to narrow the gap between the two domains. It mainly facilitates unified mutual information sharing both intra- and inter-samples, rather than treating them as a single feature alignment problem between modalities. Specifically, our approach includes: (i) Employing dual weight-sharing networks to optimize alignment within the sketch and image domain, which also effectively mitigates model learning saturation issues. (ii) Introducing an objective optimization function based on contrastive loss to enhance the model's ability to align features in both intra- and inter-samples. (iii) Presenting a self-supervised Multi-Scale Token Recycling (MSTR) Module featured by recycling discarded patch tokens in multi-scale features, further enhancing representation capability and retrieval performance. Our framework achieves excellent results on CNN- and ViT-based backbones. Extensive experiments demonstrate its superiority over existing methods. We also introduce Cloths-V1, the first professional fashion sketch-image dataset, utilized to validate our method and will be beneficial for other applications.

While Personalised PageRank (PPR) is widely used for ranking nodes in certain graphs, research on PPR for uncertain graphs remains limited. Real-world graphs often exhibit uncertainty in some edges with interdependent probabilities. The best-of-breed work by Kim et al.[13] proposed a fast approximate algorithm, UPPR, leveraging the Sherman-Morrison formula with singular value decomposition. However, UPPR lacks error guarantees, and struggles to scale on large graphs due to the high cost to precompute block matrix inverses over the certain part of the graph.

Measuring similarity based on network topology is a crucial task in the realm of web search. While many well-established similarity measures (e.g. SimRank) focus on assessing node-to-node similarity, capturing edge-to-edge relationships is equally important in many applications (e.g. link spam detection). However, existing node-to-node similarity measures from the SimRank family may violate the triangular inequality. When applied directly to assessing edge-to-edge similarity, such measures may fail to capture transitive relationships and misrepresent dissimilarity between nodes.

P-Rank (Penetrating-Rank) is a charming measure of structural similarity between objects based on graph topology. It recursively follows the principle that "two objects are considered similar if (a) they are referenced by similar objects and (b) they reference similar objects''. The best-known algorithm for computing P-Rank employs two repeated Singular Value Decompositions (SVDs) coupled with the Woodbury matrix identity. However, this method does not scale well on billion-sized graphs. Worse yet, this algorithm only provides a linear approximation of the P-Rank model and cannot deliver accurate P-Rank values. In this paper, we propose P-Rank+, a fast and efficient algorithm for computing P-Rank similarities, which scales well on large graphs with billions of edges. P-Rank+ leverages dimensionality reduction techniques by performing only one SVD of the graph integrated with Hadamard products in the reduced subspace. Moreover, we provide provable error guarantees for P-Rank+ computation. Experiments on various datasets validate that P-Rank+ is 1--3 orders of magnitude faster than the best-known competitor while achieving excellent scalability on massive graphs.

Role-based similarity search, predicated on the topological structure of graphs, is a highly effective and widely applicable technique for various real-world information extraction applications. Although the prominent rolebased similarity algorithm, RoleSim, successfully provides the automorphic (role) equivalence of similarity between pairs of nodes, it does not effectively differentiate nodes that exhibit exact automorphic equivalence but differ in terms of structural equivalence within a given graph. This limitation arises from disregarding most adjacency similarity information between pairs of nodes during the RoleSim computation. To address this research gap, we propose a novel single-source role similarity search algorithm, named FaRS, which employs the top Γ maximum similarity matching technique to capture more information from the classes of neighboring nodes, ensuring both automorphic equivalence and structural equivalence of role similarity. Furthermore, we establi sh the convergence of FaRS and demonstrate its adherence to various axioms, including uniqueness, symmetry, boundedness, and triangular inequality. Additionally, we introduce the Opt FaRS algorithm, which optimizes the computation of FaRS through two acceleration components: path extraction tracking and precomputation (P-speedup and Out-speedup approach). Experimental results on real datasets demonstrate that FaRS and Opt FaRS outperform baseline algorithms in terms of both accuracy and efficiency.

Many deep graph neural networks perform well in tackling semi-supervised node classification tasks. However, they often focus on learning a holistic representation for nodes, which lacks interpretability and compactness for classification purposes. In this paper, we propose a Multi-Relation Enhanced Graph Disentangled Network (MREGDN), which can effectively disentangle the latent factors that affect graph topology, while enhancing the interpretability and low-redundancy of the learned node representations for classification. There are three types of relation constraints designed elaborately to optimize the disentangled representation learning process: (a) constraints of intra-factor compactness to encourage a factor to represent a distribution, (b) constraints of inter-factor irrelevance to ensure diversity among factors, and (c) constraints of keeping inter-node similarity in different spaces to retain necessary information related to category. Extensive experiments verify that MREGDN significantly outperforms its best-known competitors on various semi-supervised node classification tasks.

The accurate prediction of traffic conditions, including speed, flow, and travel time, poses a critical challenge in urbanization that significantly impacts car owners and road administrators. However, in certain scenarios with restricted road data availability (e.g. lack of traffic light status and signal control strategies, cooperation between road administrators and third parties, etc.), it is imperative to make effective use of basic road information (e.g. historical traffic data and road connectivity) to improve both prediction accuracy and scalability on various arterial road networks against state-of-art deep learning models. In this paper, we propose a spatial-temporal learning framework TPGraph for an accurate prediction of arterial roads’ traffic data by effectively utilizing upstream and downstream road information. TPGraph is composed of three major parts: 1) A multi-scale temporal feature fusion module that utilizes a multi-head attention mechanism to integrate recently-periodic features, daily-periodic features, and weekly-periodic features; 2) A multi-graph convolution module that employs graph fusion and graph convolution networks to capture richer spatial semantics, and 3) A dynamic spatial-temporal prediction module that leverages a spatial-temporal transformer for single or multiple traffic-state predictions. Our proposed framework, TPGraph, leverages just multi-scale historical traffic conditions and readily accessible spatial factors as input to generate accurate predictions of future traffic conditions. We mainly evaluate the performance of our approach through multi-step prediction experiments conducted at hourly intervals, forecasting travel time or travel speed for each road at 15 mins, 30 mins, and 1 hour. Furthermore, we conduct extensive experiments on real-world arterial road datasets to demonstrate the superior predictive performance of TPGraph compared to existing methods.

The “mind-controlling” capability has always been in mankind's fantasy. With the recent advancements in electroencephalograph (EEG) techniques, brain-computer interface (BCI) researchers have explored some solutions to allow individuals to perform various tasks using their minds. However, the commercial off-the-shelf devices to run accurate EEG signal collection are usually expensive and the comparably cheaper devices can only present coarse results, which prevents the practical application of these devices in domestic services. To tackle this challenge, we propose and develop an end-to-end solution that enables fine brain-robot interaction (BRI) through embedded learning of coarse EEG signals from low-cost devices, namely PerBCI, so that people having difficulty moving, such as the elderly, can mind command and control a robot to perform some basic household tasks. Our contributions are three folds: 1) We present a stacked long short-term memory (BiLSTM) structure, along with specific pre-processing techniques to handle the time-dependency of EEG signals and their classification. 2) We propose a personalized design to adaptively capture multiple features and achieve accurate recognition of individual EEG signals by enhancing the signal interpretation of BiLSTM with an attention mechanism. 3) We develop a low-cost, real-time and end-to-end BRI system that can run our PerBCI models and algorithms in the embedded robot platform to perform more than one type of domestic task based on the users' EEG signal inputs. Our real-world experiments with elderly participants of diverse backgrounds in a home setting and system comparison with other approaches show that the proposed end-to-end solution with low cost can achieve satisfactory run-time speed, accuracy and energy-efficiency.

Non-negative Matrix Factorization (NMF) has been widely adopted for link prediction, aiming at finding multiple low-dimensional matrices whose product approximates the adjacency matrix of a network. Most existing NMF-based models incorporate auxiliary information with well-defined geometric meanings, but there is no evidence that they have reasonable mathematical interpretations. In this paper, we propose a model, NMF-CR, that incorporates both row-space and column-space information into the NMF framework. NMF-CR not only carries well-defined geometric meanings but also boasts a reasonable mathematical interpretation. Moreover, we provide efficient updating rules to infer the parameters of NMF-CR with guaranteed convergence. Extensive experiments demonstrate that our model achieves higher prediction accuracy than its competitors.

Abstract Semi-supervised node classification is an important task that aims at classifying nodes based on the graph structure, node features, and class labels for a subset of nodes. While most graph convolutional networks (GCNs) perform well when an ample number of labeled nodes are available, they often degenerate when the amount of labeled data is limited. To address this problem, we propose a scheme, namely, Individuality-enhanced and Multi-granularity Consistency-preserving graph neural Network (IMCN), which can alleviate the problem of losing individual information within the encoder while providing a reliable supervised signal for learning purposes. First, one simple encoder based on node features only is integrated to enhance node individuality and amend node commonality learned by the GCN-based encoder. Then, three constraints are defined at different levels of granularity, encompassing node embedding agreement, semantic class alignment, and node-to-class distribution identity. They can maintain the consistency between the individuality and commonality of nodes and be leveraged as latent supervised signals for learning representative embeddings. Finally, the trade-off between the individuality and commonality of nodes captured by two encoders is taken into consideration for node classification. Extensive experiments on six real-world datasets have been conducted to validate the superiority of IMCN against state-of-the-art baselines in handling node classification tasks with scarce labeled data. Graphical abstract

Local differential privacy (LDP) is promising for private streaming data collection and analysis. However, existing few LDP studies over streams either apply to finite streams only or may suffer from insufficient protection. This paper investigates this problem by proposing LDP-IDS, a novel w-event LDP paradigm to provide practical privacy guarantee for infinite streams. By constructing a unified error analysis, we adapt the existing budget division framework in centralized differential privacy (CDP) for LDP-IDS, which however incurs prohibitive noise and expensive communication cost. To this end, we propose a novel and extensible framework of population division and recycling, as well as online adaptive population division algorithms for LDP-IDS. We provide theoretical guarantees and demonstrate, through extensive discussions, that our proposed framework not only achieves significant reduction in utility loss and communication overhead, but also enjoys great compatibility for varied analytic tasks and flexibility of incorporating ideas of many existing stream algorithms. Extensive experiments on synthetic and real-world datasets validate the high effectiveness, efficiency, and flexibility of our proposed framework and methods.

Myriads of web applications in the Big Data era demand an effective measure of similarity based on billion-scale network structures, e.g., collaborative filtering. Recently, CoSimRank has been devised as a promising graph-theoretic similarity model, which iteratively captures the notion that “two distinct nodes are evaluated as similar if they are connected with similar nodes”. However, the existing CoSimRank model for assessing similarities may either yield unsatisfactory results or rather cost-inhibitive, rendering it impractical in massive graphs. In this paper, we propose CoSimHeat, a novel scalable graph-theoretic similarity model based on heat diffusion. Specifically, we first formulate CoSimHeat model by taking advantage of heat diffusion to emulate the activities of similarity propagations on the Web. Then, we show that the similarities produced by CoSimHeat are more satisfactory than those from CoSimRank families since CoSimHeat fulfils four axioms that an ideal similarity model should satisfy while circumventing the “dead-loop” problem of CoSimRank. Next, we propose a fast algorithm to substantially accelerate CoSimHeat computations on billion-sized graphs, with guarantees of accuracy. Our experiments on various datasets validate that CoSimHeat achieves higher accuracy and is order-of-magnitude faster than state-of-the-art competitors.

The high demand for ubiquitous availability of reliable parking spaces in cities faces challenges on timely information sharing and low-cost infrastructure deployment. In this paper, we propose a mobile crowdsensing system, namely ParkHop, to aggregate on-street and roadside parking space information through sensorless sensing, and disseminate this information to urban drivers in a resilient manner. ParkHop targets special social groups that have stable work routines to serve as crowd workers. We propose a crowdsensing algorithm employing a joint estimator to process crowdsensed data, and evaluate the reliability of crowd workers based on the veracity of their answers to a series of control questions. In addition, the specific worker selection method to speed up the crowdsensing process and incentive scheme to achieve fair reward distribution have been carefully designed in ParkHop. Our system disseminates the availability of parking spaces and their up-to-date price information to drivers with on-demand needs via a publish-subscribe messaging pattern. The efficacy of ParkHop for aggregation and dissemination of parking space information has been evaluated in both real-world tests and simulations. Our results show the system is robust and agile enough to cope with different crowdsensing scenarios.

SimRank is an attractive link-based similarity measure used in fertile fields of Web search and sociometry. However, the existing deterministic method by Kusumoto et al. [ 24 ] for retrieving SimRank does not always produce high-quality similarity results, as it fails to accurately obtain diagonal correction matrix D. Moreover, SimRank has a “connectivity trait” problem: increasing the number of paths between a pair of nodes would decrease its similarity score. The best-known remedy, SimRank++ [ 1 ], cannot completely fix this problem, since its score would still be zero if there are no common in-neighbors between two nodes. In this article, we study fast high-quality link-based similarity search on billion-scale graphs. (1) We first devise a “varied-D” method to accurately compute SimRank in linear memory. We also aggregate duplicate computations, which reduces the time of [ 24 ] from quadratic to linear in the number of iterations. (2) We propose a novel “cosine-based” SimRank model to circumvent the “connectivity trait” problem. (3) To substantially speed up the partial-pairs “cosine-based” SimRank search on large graphs, we devise an efficient dimensionality reduction algorithm,PSR#, with guaranteed accuracy. (4) We give mathematical insights to the semantic difference between SimRank and its variant, and correct an argument in [ 24 ] that “ifDis replaced by a scaled identity matrix (1-Ɣ)I, their top-K rankings will not be affected much”. (5) We propose a novel method that can accurately convert from Li et al. SimRank ~{S} to Jeh and Widom’s SimRankS. (6) We proposeGSR#, a generalisation of our “cosine-based” SimRank model, to quantify pairwise similarities across two distinct graphs, unlike SimRank that would assess nodes across two graphs as completely dissimilar. Extensive experiments on various datasets demonstrate the superiority of our proposed approaches in terms of high search quality, computational efficiency, accuracy, and scalability on billion-edge graphs.

As sensor-based networks become more prevalent, scaling to unmanageable numbers or deployed in difficult to reach areas, real-time failure localisation is becoming essential for continued operation. Network tomography, a system and application-independent approach, has been successful in localising complex failures (i.e., observable by end-to-end global analysis) in traditional networks. Applying network tomography to wireless sensor networks (WSNs), however, is challenging. First, WSN topology changes due to environmental interactions (e.g., interference). Additionally, the selection of devices for running network monitoring processes (monitors) is an NP-hard problem. Monitors observe end-to-end in-network properties to identify failures, with their placement impacting the number of identifiable failures. Since monitoring consumes more in-node resources, it is essential to minimise their number while maintaining network tomography’s effectiveness. Unfortunately, state-of-the-art solutions solve this optimisation problem using time-consuming greedy heuristics. In this article, we propose two solutions for efficiently applying Network Tomography in WSNs: a graph compression scheme, enabling faster monitor placement by reducing the number of edges in the network, and an adaptive monitor placement algorithm for recovering the monitor placement given topology changes. The experiments show that our solution is at least 1,000× faster than the state-of-the-art approaches and efficiently copes with topology variations in large-scale WSNs.

Abstract RoleSim and SimRank are among the popular graph-theoretic similarity measures with many applications in, e.g., web search, collaborative filtering, and sociometry. While RoleSim addresses the automorphic (role) equivalence of pairwise similarity which SimRank lacks, it ignores the neighboring similarity information out of the automorphically equivalent set. Consequently, two pairs of nodes, which are not automorphically equivalent by nature, cannot be well distinguished by RoleSim if the averages of their neighboring similarities over the automorphically equivalent set are the same. To alleviate this problem: 1) We propose a novel similarity model, namely RoleSim*, which accurately evaluates pairwise role similarities in a more comprehensive manner. RoleSim* not only guarantees the automorphic equivalence that SimRank lacks, but also takes into account the neighboring similarity information outside the automorphically equivalent sets that are overlooked by RoleSim. 2) We prove the existence and uniqueness of the RoleSim* solution, and show its three axiomatic properties (i.e., symmetry, boundedness, and non-increasing monotonicity). 3) We provide a concise bound for iteratively computing RoleSim* formula, and estimate the number of iterations required to attain a desired accuracy. 4) We induce a distance metric based on RoleSim* similarity, and show that the RoleSim* metric fulfills the triangular inequality, which implies the sum-transitivity of its similarity scores. 5) We present a threshold-based RoleSim* model that reduces the computational time further with provable accuracy guarantee. 6) We propose a single-source RoleSim* model, which scales well for sizable graphs. 7) We also devise methods to scale RoleSim* based search by incorporating its triangular inequality property with partitioning techniques. Our experimental results on real datasets demonstrate that RoleSim* achieves higher accuracy than its competitors while scaling well on sizable graphs with billions of edges.

The time series data generated by massive sensors in Internet of Things (IoT) is extremely dynamic, heterogeneous, large scale and time-dependent. It poses great challenges (e.g. accuracy, reliability, stability) on the real-time analysis and decision making for different IoT applications. In this paper, we design, implement and evaluate EdgeLSTM, a unified data-driven system to enhance IoT computing at the network edge. The EdgeLSTM leverages the grid long short-term memory (Grid LSTM) to provide an agile solution for both deep and sequential computation, therefore can address important features such as large-scale, variety, time dependency and real time in IoT data. Our system exploits the advantages of Grid LSTM network and extends it with a multiclass support vector machine by rigorous regularization and optimization approaches, which not only has strong prediction capability of time series data, but also achieves fine-grained multiple classification through the predictive error. We deploy the EdgeLSTM into four IoT applications, including data prediction, anomaly detection, network maintenance and mobility management by extensive experiments. Our evaluation results of real-world time series data with different short-term and long-term time dependency from these typical IoT applications show that our EdgeLSTM system can guarantee robust performance in IoT computing.

Person re-identification (person Re-Id) aims to retrieve the pedestrian images of the same person that captured by disjoint and non-overlapping cameras. Lots of researchers recently focused on this hot issue and proposed deep learning based methods to enhance the recognition rate in a supervised or unsupervised manner . However,there are two limitations that cannot be ignored: firstly, compared with other image retrieval benchmarks, the size of existing person Re-Id datasets is far from meeting the requirement, which cannot provide sufficient pedestrian samples for the training of deep model; secondly, the samples in existing datasets do not have sufficient human motions or postures coverage to provide more priori knowledges for learning. In this paper, we introduce a novel unsupervised pose augmentation cross-view person Re-Id scheme called PAC-GAN to overcome these limitations. We firstly present the formal definition of cross-view pose augmentation and then propose the framework of PAC-GAN that is a novel conditional generative adversarial network (CGAN) based approach to improve the performance of unsupervised corss-view person Re-Id. Specifically, the pose generation model in PAC-GAN called CPG-Net is to generate enough quantity of pose-rich samples from original image and skeleton samples. The pose augmentation dataset is produced by combining the synthesized pose-rich samples with the original samples, which is fed into the corss-view person Re-Id model named Cross-GAN. Besides, we use weight-sharing strategy in the CPG-Net to improve the quality of new generated samples. To the best of our knowledge, we are the first to enhance the unsupervised cross-view person Re-Id by pose augmentation, and the results of extensive experiments show that the proposed scheme can combat the state-of-the-arts with recognition rate.

The data generated by millions of sensors in the industrial Internet of Things (IIoT) are extremely dynamic, heterogeneous, and large scale and pose great challenges on the real-time analysis and decision making for anomaly detection in the IIoT. In this article, we propose a long short-term memory (LSTM)-Gauss-NBayes method, which is a synergy of the long short-term memory neural network (LSTM-NN) and the Gaussian Bayes model for outlier detection in the IIoT. In a nutshell, the LSTM-NN builds a model on normal time series. It detects outliers by utilizing the predictive error for the Gaussian Naive Bayes model. Our method exploits advantages of both LSTM and Gaussian Naive Bayes models, which not only has strong prediction capability of LSTM for future time point data, but also achieves an excellent classification performance of the Gaussian Naive Bayes model through the predictive error. We evaluate our approaches on three real-life datasets that involve both long-term and short-term time dependence. Empirical studies demonstrate that our proposed techniques outperform the best-known competitors, which is a preferable choice for detecting anomalies.

Microblog platforms have been extremely popular in the big data era due to its real-time diffusion of information. It's important to know what anomalous events are trending on the social network and be able to monitor their evolution and find related anomalies. In this paper we demonstrate RING, a real-time emerging anomaly monitoring system over microblog text streams. RING integrates our efforts on both emerging anomaly monitoring research and system research. From the anomaly monitoring perspective, RING proposes a graph analytic approach such that (1) RING is able to detect emerging anomalies at an earlier stage compared to the existing methods, (2) RING is among the first to discover emerging anomalies correlations in a streaming fashion, (3) RING is able to monitor anomaly evolutions in real-time at different time scales from minutes to months. From the system research perspective, RING (1) optimizes time-ranged keyword query performance of a full-text search engine to improve the efficiency of monitoring anomaly evolution, (2) improves the dynamic graph processing performance of Spark and implements our graph stream model on it, As a result, RING is able to process big data to the entire Weibo or Twitter text stream with linear horizontal scalability. The system clearly presents its advantages over existing systems and methods from both the event monitoring perspective and the system perspective for the emerging event monitoring task.

Many web applications demand a measure of similarity between two entities, such as collaborative filtering, web document ranking, linkage prediction, and anomaly detection. P-Rank (Penetrating-Rank) has been accepted as a promising graph-based similarity measure, as it provides a comprehensive way of encoding both incoming and outgoing links into assessment. However, the existing method to compute P-Rank is iterative in nature and rather cost-inhibitive. Moreover, the accuracy estimate and stability issues for P-Rank computation have not been addressed. In this article, we consider the optimization techniques for P-Rank search that encompasses its accuracy, stability, and computational efficiency. (1) The accuracy estimation is provided for P-Rank iterations, with the aim to find out the number of iterations, k , required to guarantee a desired accuracy. (2) A rigorous bound on the condition number of P-Rank is obtained for stability analysis. Based on this bound, it can be shown that P-Rank is stable and well-conditioned when the damping factors are chosen to be suitably small. (3) Two matrix-based algorithms, applicable to digraphs and undirected graphs, are, respectively, devised for efficient P-Rank computation, which improves the computational time from O ( kn 3 ) to O (υ n 2 +υ 6 ) for digraphs, and to O (υ n 2 ) for undirected graphs, where n is the number of vertices in the graph, and υ (≪ n ) is the target rank of the graph. Moreover, our proposed algorithms can significantly reduce the memory space of P-Rank computations from O ( n 2 ) to O (υ n +υ 4 ) for digraphs, and to O (υ n ) for undirected graphs, respectively. Finally, extensive experiments on real-world and synthetic datasets demonstrate the usefulness and efficiency of the proposed techniques for P-Rank similarity assessment on various networks.

Given a graph, how can we quantify similarity between two nodes in an effective and scalable way? SimRank is an attractive measure of pairwise similarity based on graph topologies. Its underpinning philosophy that “two nodes are similar if they are pointed to (have incoming edges) from similar nodes” can be regarded as an aggregation of similarities based on incoming paths. Despite its popularity in various applications (e.g., web search and social networks), SimRank has an undesirable trait, i.e., “zero-similarity”: it accommodates only the paths of equal length from a common “center” node, whereas a large portion of other paths are fully ignored. In this paper, we propose an effective and scalable similarity model, SimRank*, to remedy this problem. (1) We first provide a sufficient and necessary condition of the “zero-similarity” problem that exists in Jeh and Widom’s SimRank model, Li et al. ’s SimRank model, Random Walk with Restart (RWR), and ASCOS++. (2) We next present our treatment, SimRank*, which can resolve this issue while inheriting the merit of the simple SimRank philosophy. (3) We reduce the series form of SimRank* to a closed form, which looks simpler than SimRank but which enriches semantics without suffering from increased computational overhead. This leads to an iterative form of SimRank*, which requires O(Knm) time and $$O(n^2)$$ memory for computing all $$(n^2)$$ pairs of similarities on a graph of n nodes and m edges for K iterations. (4) To improve the computational time of SimRank* further, we leverage a novel clustering strategy via edge concentration. Due to its NP-hardness, we devise an efficient heuristic to speed up all-pairs SimRank* computation to $$O(Kn{\tilde{m}})$$ time, where $${\tilde{m}}$$ is generally much smaller than m. (5) To scale SimRank* on billion-edge graphs, we propose two memory-efficient single-source algorithms, i.e., ss-gSR* for geometric SimRank*, and ss-eSR* for exponential SimRank*, which can retrieve similarities between all n nodes and a given query on an as-needed basis. This significantly reduces the $$O(n^2)$$ memory of all-pairs search to either $$O(Kn + {\tilde{m}})$$ for geometric SimRank*, or $$O(n + {\tilde{m}})$$ for exponential SimRank*, without any loss of accuracy, where $${\tilde{m}} \ll n^2$$ . (6) We also compare SimRank* with another remedy of SimRank that adds self-loops on each node and demonstrate that SimRank* is more effective. (7) Using real and synthetic datasets, we empirically verify the richer semantics of SimRank*, and validate its high computational efficiency and scalability on large graphs with billions of edges.

In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is updated with new edges arriving over time, it is cost-inhibitive to recompute all CoSimRank scores from scratch, which is impractical. In this study, we propose a fast dynamic scheme, \DCoSim for accurate CoSimRank search over evolving graphs. Based on \DCoSim, we also propose a fast scheme, \FCoSim, that greatly accelerates CoSimRank search over static graphs. Our theoretical analysis shows that \DCoSim and \FCoSim guarantee the exactness of CoSimRank scores. On the static graph G, to efficiently retrieve CoSimRank scores $\mathbfS $, \FCoSim is based on three ideas: (i) It first finds a "spanning polytree»» T over G. (ii) On T, a fast algorithm is designed to compute the CoSimRank scores $\mathbfS (T)$ over the "spanning polytree»» T. (iii) On G, \DCoSim is employed to compute the changes of $\mathbfS (T)$ in response to the delta graph $(G øminus T)$. Experimental evaluations verify the superiority of \DCoSim over evolving graphs, and the fast speedup of \FCoSim on large-scale static graphs against its competitors, without any loss of accuracy.

High-dimensional crowdsourced data collected from numerous users produces rich knowledge about our society; however, it also brings unprecedented privacy threats to the participants. Local differential privacy (LDP), a variant of differential privacy, is recently proposed as a state-of-the-art privacy notion. Unfortunately, achieving LDP on high-dimensional crowdsourced data publication raises great challenges in terms of both computational efficiency and data utility. To this end, based on the expectation maximization (EM) algorithm and Lasso regression, we first propose efficient multi-dimensional joint distribution estimation algorithms with LDP. Then, we develop a local differentially private high-dimensional data publication algorithm (LoPub) by taking advantage of our distribution estimation techniques. In particular, correlations among multiple attributes are identified to reduce the dimensionality of crowdsourced data, thus speeding up the distribution learning process and achieving high data utility. Extensive experiments on real-world datasets demonstrate that our multivariate distribution estimation scheme significantly outperforms existing estimation schemes in terms of both communication overhead and estimation speed. Moreover, LoPub can keep, on average, 80% and 60% accuracy over the released datasets in terms of support vector machine and random forest classification, respectively.

SimRank is an appealing pair-wise similarity measure based on graph structure. It iteratively follows the intuition that two nodes are assessed as similar if they are pointed to by similar nodes. Many real graphs are large, and links are constantly subject to minor changes. In this article, we study the efficient dynamical computation of all-pairs SimRanks on time-varying graphs. Existing methods for the dynamical SimRank computation [e.g., LTSF (Shao et al. in PVLDB 8(8):838–849, 2015) and READS (Zhang et al. in PVLDB 10(5):601–612, 2017)] mainly focus on top-k search with respect to a given query. For all-pairs dynamical SimRank search, Li et al.’s approach (Li et al. in EDBT, 2010) was proposed for this problem. It first factorizes the graph via a singular value decomposition (SVD) and then incrementally maintains such a factorization in response to link updates at the expense of exactness. As a result, all pairs of SimRanks are updated approximately, yielding $$O({r}^{4}n^2)$$ time and $$O({r}^{2}n^2)$$ memory in a graph with n nodes, where r is the target rank of the low-rank SVD. Our solution to the dynamical computation of SimRank comprises of five ingredients: (1) We first consider edge update that does not accompany new node insertions. We show that the SimRank update $${\varvec{\Delta }}{} \mathbf{S}$$ in response to every link update is expressible as a rank-one Sylvester matrix equation. This provides an incremental method requiring $$O(Kn^2)$$ time and $$O(n^2)$$ memory in the worst case to update $$n^2$$ pairs of similarities for K iterations. (2) To speed up the computation further, we propose a lossless pruning strategy that captures the “affected areas” of $${\varvec{\Delta }}{} \mathbf{S}$$ to eliminate unnecessary retrieval. This reduces the time of the incremental SimRank to $$O(K(m+|{\textsf {AFF}}|))$$ , where m is the number of edges in the old graph, and $$|{\textsf {AFF}}| \ (\le n^2)$$ is the size of “affected areas” in $${\varvec{\Delta }}{} \mathbf{S}$$ , and in practice, $$|{\textsf {AFF}}| \ll n^2$$ . (3) We also consider edge updates that accompany node insertions, and categorize them into three cases, according to which end of the inserted edge is a new node. For each case, we devise an efficient incremental algorithm that can support new node insertions and accurately update the affected SimRanks. (4) We next study batch updates for dynamical SimRank computation, and design an efficient batch incremental method that handles “similar sink edges” simultaneously and eliminates redundant edge updates. (5) To achieve linear memory, we devise a memory-efficient strategy that dynamically updates all pairs of SimRanks column by column in just $$O(Kn+m)$$ memory, without the need to store all $$(n^2)$$ pairs of old SimRank scores. Experimental studies on various datasets demonstrate that our solution substantially outperforms the existing incremental SimRank methods and is faster and more memory-efficient than its competitors on million-scale graphs.

Random Walk with Restart (RWR) is an appealing measure of proximity between nodes based on graph structures. Since real graphs are often large and subject to minor changes, it is prohibitively expensive to recompute proximities from scratch. Previous methods use LU decomposition and degree reordering heuristics, entailing O(|ν|3) time and O(|ν|2) memory to compute all (|ν|2) pairs of node proximities in a static graph. In this paper, a dynamic scheme to assess RWR proximities is proposed: (1) For unit update, we characterize the changes to all-pairs proximities as the outer product of two vectors. We notice that the multiplication of an RWR matrix and its transition matrix, unlike traditional matrix multiplications, is commutative. This can greatly reduce the computation of all-pairs proximities from O(|ν|3) to O(|Δ|) time for each update without loss of accuracy, where |Δ| (≪|V|2) is the number of affected proximities. (2) To avoid O(|V|2) memory for all pairs of outputs, we also devise efficient partitioning techniques for our dynamic model, which can compute all pairs of proximities segment-wisely within O(I|V|) memory and O([|V|/l]) I/O costs, where 1 ≤ I ≤ |V| is a user-controlled trade-off between memory and I/O costs. (3) For bulk updates, we also devise aggregation and hashing methods, which can discard many unnecessary updates further and handle chunks of unit updates simultaneously. Our experimental results on various datasets demonstrate that our methods can be 1-2 orders of magnitude faster than other competitors while securing scalability and exactness.

Summary As a new form of social media, microblogs (e.g., Twitter and Weibo) are playing an important role in people's daily life. With the rise in popularity and size of microblogs, there is a need for distributed approaches that can detect bursty event with low latency from the short‐text data stream. In this paper, we propose a distributed and incremental temporal topic model for microblogs called Bursty Event dEtection (BEE+). BEE+ is able to detect bursty events from short‐text dataset and model the temporal information. And BEE+ processes the post‐stream incrementally to track the topic drifting of events over time. Therefore, the latent semantic indices are preserved from one time period to the next. In order to achieve real‐time processing, we design a distributed execution framework based on Spark engine. To verify its ability to detect bursty event, we conduct experiments on a Weibo dataset of 6,360,125 posts. The results show that BEE+ can outperform the baselines for detecting the meaningful bursty events and track the topic drifting. Copyright © 2015 John Wiley & Sons, Ltd.

One of the important tasks in link analysis is to quantify the similarity between two objects based on hyperlink structure. SimRank is an attractive similarity measure of this type. Existing work mainly focuses on absolute SimRank scores, and often harnesses an iterative paradigm to compute them. While these iterative scores converge to exact ones with the increasing number of iterations, it is still notoriously difficult to determine how well the relative orders of these iterative scores can be preserved for a given iteration. In this paper, we propose efficient ranking criteria that can secure correct relative orders of node-pairs with respect to SimRank scores when they are computed in an iterative fashion. Moreover, we show the superiority of our criteria in harvesting top-K SimRank scores and bucket orders from a full ranking list. Finally, viable empirical studies verify the usefulness of our techniques for SimRank top-K ranking and bucket ordering.

SimRank is an influential link-based similarity measure that has been used in many fields of Web search and sociometry. The best-of-breed method by Kusumoto et. al., however, does not always deliver high-quality results, since it fails to accurately obtain its diagonal correction matrix D. Besides, SimRank is also limited by an unwanted "connectivity trait": increasing the number of paths between nodes a and b often incurs a decrease in score s(a,b). The best-known solution, SimRank++, cannot resolve this problem, since a revised score will be zero if a and b have no common in-neighbors. In this paper, we consider high-quality similarity search. Our scheme, SR#, is efficient and semantically meaningful: (1) We first formulate the exact D, and devise a "varied-D" method to accurately compute SimRank in linear memory. Moreover, by grouping computation, we also reduce the time of from quadratic to linear in the number of iterations. (2) We design a "kernel-based" model to improve the quality of SimRank, and circumvent the "connectivity trait" issue. (3) We give mathematical insights to the semantic difference between SimRank and its variant, and correct an argument: "if D is replaced by a scaled identity matrix, top-K rankings will not be affected much". The experiments confirm that SR# can accurately extract high-quality scores, and is much faster than the state-of-the-art competitors.

The assessment of node-to-node similarities based on graph topology arises in a myriad of applications, e.g. , web search. SimRank is a notable measure of this type, with the intuition that "two nodes are similar if their in-neighbors are similar". While most existing work retrieving SimRank only considers all-pairs SimRank s (*, *) and single-source SimRank s (*, j ) (scores between every node and query j ), there are appealing applications for partial-pairs SimRank, e.g. , similarity join. Given two node subsets A and B in a graph, partial-pairs SimRank assessment aims to retrieve only { s ( a , b )} ∀ a ε A ,∀ b ε B . However, the best-known solution appears not self-contained since it hinges on the premise that the SimRank scores with node-pairs in an h -go cover set must be given beforehand. This paper focuses on efficient assessment of partial-pairs SimRank in a self-contained manner. (1) We devise a novel "seed germination" model that computes partial-pairs SimRank in O ( k | E | min{| A |, | B |}) time and O (| E | + k | V |) memory for k iterations on a graph of | V | nodes and | E | edges. (2) We further eliminate unnecessary edge access to improve the time of partial-pairs SimRank to O ( m min{| A |, | B |}), where m ≤ min{ k | E |, Δ 2 k }, and Δ is the maximum degree. (3) We show that our partial-pairs SimRank model also can handle the computations of all-pairs and single-source SimRanks. (4) We empirically verify that our algorithms are (a) 38x faster than the best-known competitors, and (b) memory-efficient, allowing scores to be assessed accurately on graphs with tens of millions of links.

SimRank is a powerful model for assessing vertex-pair similarities in a graph. It follows the concept that two vertices are similar if they are referenced by similar vertices. The prior work [18] exploits partial sums memoization to compute SimRank in O(Kmn) time on a graph of n vertices and m edges, for K iterations. However, computations among different partial sums may have redundancy. Besides, to guarantee a given accuracy ε, the existing SimRank needs K = [log C alterations, where C is a damping factor, but the geometric rate of convergence is slow if a high accuracy is expected. In this paper, (1) a novel clustering strategy is proposed to eliminate duplicate computations occurring in partial sums, and an efficient algorithm is then devised to accelerate SimRank computation to O(Kd'n2) time, where d' is typically much smaller than mn. (2) A new differential SimRank equation is proposed, which can represent the SimRank matrix as an exponential sum of transition matrices, as opposed to the geometric sum of the conventional counterpart. This leads to a further speedup in the convergence rate of SimRank iterations. (3) In bipartite domains, a novel finer-grained partial max clustering method is developed to speed up the computation of the Minimax SimRank variation from O(Kmn) to O(Km'n) time, where m' (≤m) is the number of edges in a reduced graph after edge clustering, which can be typically much smaller than m. Using real and synthetic data, we empirically verify that (1) our approach of partial sums sharing outperforms the best known algorithm by up to one order of magnitude; (2) the revised notion of SimRank further achieves a 5X speedup on large graphs while also fairly preserving the relative order of original SimRank scores; (3) our finer-grained partial max memoization for the Minimax SimRank variation in bipartite domains is 5X-12X faster than the baselines.

SimRank is an arresting measure of node-pair similarity based on hyperlinks. It iteratively follows the concept that 2 nodes are similar if they are referenced by similar nodes. Real graphs are often large, and links constantly evolve with small changes over time. This paper considers fast incremental computations of SimRank on link-evolving graphs. The prior approach [12] to this issue factorizes the graph via a singular value decomposition (SVD) first, and then incrementally maintains this factorization for link updates at the expense of exactness. Consequently, all node-pair similarities are estimated in O(r4n2) time on a graph of n nodes, where r is the target rank of the low-rank approximation, which is not negligibly small in practice. In this paper, we propose a novel fast incremental paradigm. (1) We characterize the SimRank update matrix ΔS, in response to every link update, via a rank-one Sylvester matrix equation. By virtue of this, we devise a fast incremental algorithm computing similarities of n2node-pairs in O(Kn2) time for K iterations. (2) We also propose an effective pruning technique capturing the “affected areas” of ΔS to skip unnecessary computations, without loss of exactness. This can further accelerate the incremental SimRank computation to O(K(nd+|AFF|)) time, where d is the average in-degree of the old graph, and |AFF| (≤ n2) is the size of “affected areas” in ΔS, and in practice, |AFF| ≪ n2. Our empirical evaluations verify that our algorithm (a) outperforms the best known link-update algorithm [12], and (b) runs much faster than its batch counterpart when link updates are small.

SimRank is an attractive structural-context measure of similarity between two objects in a graph. It recursively follows the intuition that "two objects are similar if they are referenced by similar objects". The best known matrix-based method [1] for calculating SimRank, however, implies an assumption that the graph is non-singular, its adjacency matrix is invertible. In reality, non-singular graphs are very rare; such an assumption in [1] is too restrictive in practice. In this paper, we provide a treatment of [1], by supporting similarity assessment on non-invertible adjacency matrices. Assume that a singular graph G has n nodes, with r(

SimRank has been a powerful model for assessing the similarity of pairs of vertices in a graph. It is based on the concept that two vertices are similar if they are referenced by similar vertices. Due to its self-referentiality, fast SimRank computation on large graphs poses significant challenges. The state-of-the-art work [17] exploits partial sums memorization for computing SimRank in O(Kmn) time on a graph with n vertices and m edges, where K is the number of iterations. Partial sums memorizing can reduce repeated calculations by caching part of similarity summations for later reuse. However, we observe that computations among different partial sums may have duplicate redundancy. Besides, for a desired accuracy ϵ, the existing SimRank model requires K = [logCϵ] iterations [17], where C is a damping factor. Nevertheless, such a geometric rate of convergence is slow in practice if a high accuracy is desirable. In this paper, we address these gaps. (1) We propose an adaptive clustering strategy to eliminate partial sums redundancy (i.e., duplicate computations occurring in partial sums), and devise an efficient algorithm for speeding up the computation of SimRank to 0(Kd'n2) time, where d' is typically much smaller than the average in-degree of a graph. (2) We also present a new notion of SimRank that is based on a differential equation and can be represented as an exponential sum of transition matrices, as opposed to the geometric sum of the conventional counterpart. This leads to a further speedup in the convergence rate of SimRank iterations. (3) Using real and synthetic data, we empirically verify that our approach of partial sums sharing outperforms the best known algorithm by up to one order of magnitude, and that our revised notion of SimRank further achieves a 5X speedup on large graphs while also fairly preserving the relative order of original SimRank scores.

Network streams have become ubiquitous in recent years because of many dynamic applications. Such streams may show localized regions of activity and evolution because of anomalous events. This paper will present methods for dynamically determining anomalous hot spots from network streams. These are localized regions of sudden activity or change in the underlying network. We will design a localized principal component analysis algorithm, which can continuously maintain the information about the changes in the different neighborhoods of the network. We will use a fast incremental eigenvector update algorithm based on von Mises iterations in a lazy way in order to efficiently maintain local correlation information. This is used to discover local change hotspots in dynamic streams. We will finally present an experimental study to demonstrate the effectiveness and efficiency of our approach.

Random Walk with Restart (RWR) has become an appealing measure of node proximities in emerging applications \eg recommender systems and automatic image captioning. In practice, a real graph is typically large, and is frequently updated with small changes. It is often cost-inhibitive to recompute proximities from scratch via \emph{batch} algorithms when the graph is updated. This paper focuses on the incremental computations of RWR in a dynamic graph, whose edges often change over time. The prior attempt of RWR [1] deploys \kdash to find top-$k$ highest proximity nodes for a given query, which involves a strategy to incrementally \emph{estimate} upper proximity bounds. However, due to its aim to prune needless calculation, such an incremental strategy is \emph{approximate}: in $O(1)$ time for each node. The main contribution of this paper is to devise an \emph{exact} and fast incremental algorithm of RWR for edge updates. Our solution, \IRWR\!, can incrementally compute any node proximity in $O(1)$ time for each edge update without loss of exactness. The empirical evaluations show the high efficiency and exactness of \IRWR for computing proximities on dynamic networks against its batch counterparts.

Similarity assessment is one of the core tasks in hyperlink analysis. Recently, with the proliferation of applications, e.g. , web search and collaborative filtering, SimRank has been a well-studied measure of similarity between two nodes in a graph. It recursively follows the philosophy that "two nodes are similar if they are referenced (have incoming edges) from similar nodes", which can be viewed as an aggregation of similarities based on incoming paths. Despite its popularity, SimRank has an undesirable property, i.e. , "zero-similarity": It only accommodates paths with equal length from a common "center" node. Thus, a large portion of other paths are fully ignored. This paper attempts to remedy this issue. (1) We propose and rigorously justify SimRank*, a revised version of SimRank, which resolves such counter-intuitive "zero-similarity" issues while inheriting merits of the basic SimRank philosophy. (2) We show that the series form of SimRank* can be reduced to a fairly succinct and elegant closed form, which looks even simpler than SimRank, yet enriches semantics without suffering from increased computational cost. This leads to a fixed-point iterative paradigm of SimRank* in O ( Knm ) time on a graph of n nodes and m edges for K iterations, which is comparable to SimRank. (3) To further optimize SimRank* computation, we leverage a novel clustering strategy via edge concentration. Due to its NP-hardness, we devise an efficient and effective heuristic to speed up SimRank* computation to O ( Kn m) time, where m is generally much smaller than m. (4) Using real and synthetic data, we empirically verify the rich semantics of SimRank*, and demonstrate its high computation efficiency.

Unlike traditional RGB video, Kinect-like depth is characterized by its large variation range and instability. As a result, traditional video compression algorithms cannot be directly applied to Kinect-like depth compression with respect to coding efficiency. In this paper, we propose a lossy Kinect-like depth compression framework based on the existing codecs, aiming to enhance the coding efficiency while preserving the depth features for further applications. In the proposed framework, the Kinect-like depth is reformed first by divisive normalized bilateral filter (DNBL) to suppress the depth noises caused by disparity normalization, and then block-level depth padding is implemented for invalid depth region compensation in collaboration with mask coding to eliminate the sharp variation caused by depth measurement failures. Before the traditional video coding, the inter-frame correlation of reformed depth is explored by proposed 2D+T prediction, in which depth volume is developed to simulate 3D volume to generate pseudo 3D prediction reference for depth uniqueness detection. The unique depth region, called active region is fed into the video encoder for traditional intra and inter prediction with residual coding, while the inactive region is skipped during depth coding. The experimental results demonstrate that our compression scheme can save 55%-85% in terms of bit cost and reduce coding complexity by 20%-65% in comparison with the traditional video compression algorithms. The visual quality of the 3D reconstruction is also improved after employing our compression scheme.

SimFusion has become a captivating measure of similarity between objects in a web graph. It is iteratively distilled from the notion that "the similarity between two objects is reinforced by the similarity of their related objects". The existing SimFusion model usually exploits the Unified Relationship Matrix (URM) to represent latent relationships among heterogeneous data, and adopts an iterative paradigm for SimFusion computation. However, due to the row normalization of URM, the traditional SimFusion model may produce the trivial solution; worse still, the iterative computation of SimFusion may not ensure the global convergence of the solution. This paper studies the revision of this model, providing a full treatment from complexity to algorithms. (1) We propose SimFusion+ based on a notion of the Unified Adjacency Matrix (UAM), a modification of the URM, to prevent the trivial solution and the divergence issue of SimFusion. (2) We show that for any vertex-pair, SimFusion+ can be performed in O(1) time and O(n) space with an O(km)-time precomputation done only once, as opposed to the O(kn3) time and O(n2) space of its traditional counterpart, where n, m, and k denote the number of vertices, edges, and iterations respectively. (3) We also devise an incremental algorithm for further improving the computation of SimFusion+ when networks are dynamically updated, with performance guarantees for similarity estimation. We experimentally verify that these algorithms scale well, and the revised notion of SimFusion is able to converge to a non-trivial solution, and allows us to identify more sensible structure information in large real-world networks.

Recent years we have witnessed the rapid advent of mobile cloud computing, in which remote software is delivered as a service and accessed by mobile device users over the Internet. However, most existing remote display technologies for high motion application (e.g, movie) have defects in latency and bandwidth. In this paper, we designed an adaptive multimedia streaming enabled remote interactivity system, Muse, to utilize remote resources with reduced display update traffic and response latency. A window-aware updating mechanism is designed as an adaptation scheme, which allows users to focus on the current application in use and also enable them to switch between applications on the fly. Besides, a windowed display encoder using H.264 video codec is integrated into the remote frame buffer protocol to achieve high performance in compression to address the high latency limitation of mobile Internet. Experimental results show that the windowed display Muse mechanism can successfully reduce network traffic, loading time and response latency of remote display and interaction. Our system can achieve in average 22fps of 1024*768 desktop multimedia playbacks with good video quality under 1 Mbit/s of bandwidth limitation.

SimRank has been proposed to rank web documents based on a graph model on hyperlinks. The existing techniques for conducting SimRank computation adopt an iteration computation paradigm. The most efficient technique has the time complexity O(n3) with the space requirement O(n2) in the worst case for each iteration where n is the number of nodes (web documents). In this paper, we propose novel optimization techniques such that each iteration takes the time O(min{n · m,nr}) and requires space O (n + m) where m is the number of edges in a web-graph model and r ≤ log27. We also show that our algorithm accelerates the convergence rate of the existing techniques. Moreover, our algorithm not only reduces the time and space complexity of the existing techniques but is also I/O efficient. We conduct extensive experiments on both synthetic and real data sets to demonstrate the efficiency and effectiveness of our iteration techniques.