results for au:Cui_P in:cs

- Nov 29 2017 cs.SI arXiv:1711.10146v2Network embedding has recently attracted lots of attentions in data mining. Existing network embedding methods mainly focus on networks with pairwise relationships. In real world, however, the relationships among data points could go beyond pairwise, i.e., three or more objects are involved in each relationship represented by a hyperedge, thus forming hyper-networks. These hyper-networks pose great challenges to existing network embedding methods when the hyperedges are indecomposable, that is to say, any subset of nodes in a hyperedge cannot form another hyperedge. These indecomposable hyperedges are especially common in heterogeneous networks. In this paper, we propose a novel Deep Hyper-Network Embedding (DHNE) model to embed hyper-networks with indecomposable hyperedges. More specifically, we theoretically prove that any linear similarity metric in embedding space commonly used in existing methods cannot maintain the indecomposibility property in hyper-networks, and thus propose a new deep model to realize a non-linear tuplewise similarity function while preserving both local and global proximities in the formed embedding space. We conduct extensive experiments on four different types of hyper-networks, including a GPS network, an online social network, a drug network and a semantic network. The empirical results demonstrate that our method can significantly and consistently outperform the state-of-the-art algorithms.
- Nov 28 2017 cs.SI arXiv:1711.09541v1Singular Value Decomposition (SVD) is a popular approach in various network applications, such as link prediction and network parameter characterization. Incremental SVD approaches are proposed to process newly changed nodes and edges in dynamic networks. However, incremental SVD approaches suffer from serious error accumulation inevitably due to approximation on incremental updates. SVD restart is an effective approach to reset the aggregated error, but when to restart SVD for dynamic networks is not addressed in literature. In this paper, we propose TIMERS, Theoretically Instructed Maximum-Error-bounded Restart of SVD, a novel approach which optimally sets the restart time in order to reduce error accumulation in time. Specifically, we monitor the margin between reconstruction loss of incremental updates and the minimum loss in SVD model. To reduce the complexity of monitoring, we theoretically develop a lower bound of SVD minimum loss for dynamic networks and use the bound to replace the minimum loss in monitoring. By setting a maximum tolerated error as a threshold, we can trigger SVD restart automatically when the margin exceeds this threshold.We prove that the time complexity of our method is linear with respect to the number of local dynamic changes, and our method is general across different types of dynamic networks. We conduct extensive experiments on several synthetic and real dynamic networks. The experimental results demonstrate that our proposed method significantly outperforms the existing methods by reducing 27% to 42% in terms of the maximum error for dynamic network reconstruction when fixing the number of restarts. Our method reduces the number of restarts by 25% to 50% when fixing the maximum error tolerated.
- Nov 27 2017 cs.SI arXiv:1711.08752v1Network embedding assigns nodes in a network to low-dimensional representations and effectively preserves the network structure. Recently, a significant amount of progresses have been made toward this emerging network analysis paradigm. In this survey, we focus on categorizing and then reviewing the current development on network embedding methods, and point out its future research directions. We first summarize the motivation of network embedding. We discuss the classical graph embedding algorithms and their relationship with network embedding. Afterwards and primarily, we provide a comprehensive overview of a large number of network embedding methods in a systematic manner, covering the structure- and property-preserving network embedding methods, the network embedding methods with side information and the advanced information preserving network embedding methods. Moreover, several evaluation approaches for network embedding and some useful online resources, including the network data sets and softwares, are reviewed, too. Finally, we discuss the framework of exploiting these network embedding methods to build an effective system and point out some potential future directions.
- Oct 18 2017 cs.CV arXiv:1710.06177v1In recent years, we witnessed a huge success of Convolutional Neural Networks on the task of the image classification. However, these models are notoriously data hungry and require tons of training images to learn the parameters. In contrast, people are far better learner who can learn a new concept very fast with only a few samples. The plausible mysteries making the difference are two fundamental learning mechanisms: learning to learn and learning by analogy. In this paper, we attempt to investigate a new human-like learning method by organically combining these two mechanisms. In particular, we study how to generalize the classification parameters of previously learned concepts to a new concept. we first propose a novel Visual Analogy Network Embedded Regression (VANER) model to jointly learn a low-dimensional embedding space and a linear mapping function from the embedding space to classification parameters for base classes. We then propose an out-of-sample embedding method to learn the embedding of a new class represented by a few samples through its visual analogy with base classes. By inputting the learned embedding into VANER, we can derive the classification parameters for the new class.These classification parameters are purely generalized from base classes (i.e. transferred classification parameters), while the samples in the new class, although only a few, can also be exploited to generate a set of classification parameters (i.e. model classification parameters). Therefore, we further investigate the fusion strategy of the two kinds of parameters so that the prior knowledge and data knowledge can be fully leveraged. We also conduct extensive experiments on ImageNet and the results show that our method can consistently and significantly outperform state-of-the-art baselines.
- Aug 23 2017 cs.CV arXiv:1708.06656v1Image classification is one of the fundamental problems in computer vision. Owing to the availability of large image datasets like ImageNet and YFCC100M, a plethora of research has been conducted to do high precision image classification and many remarkable achievements have been made. The success of most existing methods hinges on a basic hypothesis that the testing image set has the same distribution as the training image set. However, in many real applications, we cannot guarantee the validity of the i.i.d. hypothesis since the testing image set is unseen. It is thus desirable to learn an image classifier, which can perform well even in non-i.i.d. situations. In this paper, we propose a novel Causally Regularized Logistic Regression (CRLR) algorithm to address the non-i.i.d. problem without knowing testing data information by searching for causal features. The causal features refer to characteristics truly determining whether a special object belongs to a category or not. Algorithmically, we propose a causal regularizer for causal feature identification by jointly optimizing it with a logistic loss term. Assisted with the causal regularizer, we can estimate the causal contribution (causal effect) of each focal image feature (viewed as a treatment variable) by sample reweighting which ensures the distributions of all remaining image features between images with different focal feature levels are close. The resultant classifier will be based on the estimated causal contributions of the features, rather than traditional correlation-based contributions. To validate the e effectiveness of our CRLR algorithm, we manually construct a new image dataset from YFCC100M, simulating various non-i.i.d. situations in the real world, and conduct extensive experiments for image classification. Experimental results clearly demonstrate that our CRLR algorithm outperforms the state-of-the-art methods.
- Information cascades are ubiquitous in both physical society and online social media, taking on large variations in structures, dynamics and semantics. Although the dynamics and semantics of information cascades have been studied, the structural patterns and their correlations with dynamics and semantics are largely unknown. Here we explore a large-scale dataset including $432$ million information cascades with explicit records of spreading traces, spreading behaviors, information content as well as user profiles. We find that the structural complexity of information cascades is far beyond the previous conjectures. We first propose a ten-dimensional metric to quantify the structural characteristics of information cascades, reflecting cascade size, silhouette, direction and activity aspects. We find that bimodal law governs majority of the metrics, information flows in cascades have four directions, and the self-loop number and average activity of cascades follows power law. We then analyze the high-order structural patterns of information cascades. Finally, we evaluate to what extent the structural features of information cascades can explain its dynamic patterns and semantics, and finally uncover some notable implications of structural patterns in information cascades. Our discoveries also provide a foundation for the microscopic mechanisms for information spreading, potentially leading to implications for cascade prediction and outlier detection.
- Aug 23 2016 cs.GR arXiv:1608.05773v1Embedding high-dimensional data into a 2D canvas is a popular strategy for their visualization.
- May 28 2015 cs.SI physics.soc-ph arXiv:1505.07193v1Cascades are ubiquitous in various network environments. How to predict these cascades is highly nontrivial in several vital applications, such as viral marketing, epidemic prevention and traffic management. Most previous works mainly focus on predicting the final cascade sizes. As cascades are typical dynamic processes, it is always interesting and important to predict the cascade size at any time, or predict the time when a cascade will reach a certain size (e.g. an threshold for outbreak). In this paper, we unify all these tasks into a fundamental problem: cascading process prediction. That is, given the early stage of a cascade, how to predict its cumulative cascade size of any later time? For such a challenging problem, how to understand the micro mechanism that drives and generates the macro phenomenons (i.e. cascading proceese) is essential. Here we introduce behavioral dynamics as the micro mechanism to describe the dynamic process of a node's neighbors get infected by a cascade after this node get infected (i.e. one-hop subcascades). Through data-driven analysis, we find out the common principles and patterns lying in behavioral dynamics and propose a novel Networked Weibull Regression model for behavioral dynamics modeling. After that we propose a novel method for predicting cascading processes by effectively aggregating behavioral dynamics, and propose a scalable solution to approximate the cascading process with a theoretical guarantee. We extensively evaluate the proposed method on a large scale social network dataset. The results demonstrate that the proposed method can significantly outperform other state-of-the-art baselines in multiple tasks including cascade size prediction, outbreak time prediction and cascading process prediction.
- Apr 03 2015 cs.CC arXiv:1504.00442v8In this short note, the author shows that the gap problem of some $k$-CSPs with the support of its predicate the ground of a balanced pairwise independent distribution can be solved by a modified version of Hast's Algorithm BiLin that calls Charikar\&Wirth's SDP algorithm for two rounds in polynomial time, when $k$ is sufficiently large, the support of its predicate is combined by the grounds of three biased homogeneous distributions and the three biases satisfy certain conditions. To conclude, the author refutes Unique Game Conjecture, assuming $P\ne NP$.
- Aug 19 2014 physics.soc-ph cs.SI arXiv:1408.3738v2Recent empirical studies have confirmed the key roles of complex contagion mechanisms such as memory, social reinforcement, and decay effects in information diffusion and behaviour spreading. Inspired by this fact, we here propose a new agent--based model to capture the whole picture of the joint action of the three mechanisms in information spreading, by quantifying the complex contagion mechanisms as stickiness and persistence, and carry out extensive simulations of the model on various networks. By numerical simulations as well as theoretical analysis, we find that the stickiness of the message determines the critical dynamics of message diffusion on tree-like networks, whereas the persistence plays a decisive role on dense regular lattices. In either network, the greater persistence can effectively make the message more invasive. Of particular interest is that our research results renew our previous knowledge that messages can spread broader in networks with large clustering, which turns out to be only true when they can inform a non-zero fraction of the population in the limit of large system size.
- Jan 28 2014 cs.CC arXiv:1401.6520v9In this paper, the author proves a weighted $k$-CSP such that the support of its predicate can be disguised to a balanced pairwise independent distribution is approximation resistant under the standard assumption $NP\ne P$. The main ingredients of the paper include a key issue in dictator test that disguises the questions of the verifier to a balanced pairwise independent distribution and a variance-style theorem to eliminate correlation of answers of all players based on Label-Cover and its reflection version, which does not rely on Chan's technique of direct sum that requires the subgroup property. On the other hand, the author shows that the gap problem of this type of weighted $k$-CSP can be solved by Hast's Algorithm BiLin in polynomial time, when $k$ is sufficiently large, the support of its predicate is combined by the grounds of three truncated biased pairwise independent distributions and the three biases satisfy certain conditions. Thus, the author settles the longstanding open problem in computational complexity theory, i.e., $NP=P$.
- Apr 11 2012 cs.CC arXiv:1204.2026v6In this paper, the author puts forward a variation of Feige's Hypothesis, which claims that it is hard on average refuting Unbalanced Max 3-XOR under biased assignments on a natural distribution. Under this hypothesis, the author strengthens the previous known hardness for approximating Minimum Unique Game, $5/4-\epsilon$, by proving that Min 2-Lin-2 is hard to within $3/2-\epsilon$ and strengthens the previous known hardness for approximating Small Set Expansion, $4/3-\epsilon$, by proving that Min Bisection is hard to approximate within $3-\epsilon$. In addition, the author discusses the limitation of this method to show that it can strengthen the hardness for approximating Minimum Unique Game to $2-\kappa$ where $\kappa$ is a small absolute positive, but is short of proving $\omega_k(1)$ hardness for Minimum Unique Game (or Small Set Expansion), by assuming a generalization of this hypothesis on Unbalanced Max k-CSP with Samorodnitsky-Trevisan hypergraph predicate.
- Mar 01 2011 cs.CC arXiv:1102.5605v4In this paper, the author defines Generalized Unique Game Problem (GUGP), where weights of the edges are allowed to be negative. Two special types of GUGP are illuminated, GUGP-NWA, where the weights of all edges are negative, and GUGP-PWT($\rho$), where the total weight of all edges are positive and the negative-positive ratio is at most $\rho$. The author investigates the counterpart of the Unique Game Conjecture on GUGP-PWT($\rho$). The author shows that Unique Game Conjecture on GUGP-PWT(1) holds true, and Unique Game Conjecture on GUGP-PWT(1/2) holds true, if the 2-to-1 Conjecture holds true. The author poses an open problem whether Unique Game Conjecture holds true on GUGP-PWT($\rho$) with $0<\rho<1$.
- Test set with redundancy is one of the focuses in recent bioinformatics research. Set cover greedy algorithm (SGA for short) is a commonly used algorithm for test set with redundancy. This paper proves that the approximation ratio of SGA can be $(2-\frac{1}{2r})\ln n+{3/2}\ln r+O(\ln\ln n)$ by using the potential function technique. This result is better than the approximation ratio $2\ln n$ which directly derives from set multicover, when $r=o(\frac{\ln n}{\ln\ln n})$, and is an extension of the approximability results for plain test set.
- May 15 2007 cs.DS arXiv:0705.1750v6Setcover greedy algorithm is a natural approximation algorithm for test set problem. This paper gives a precise and tighter analysis of performance guarantee of this algorithm. The author improves the performance guarantee $2\ln n$ which derives from set cover problem to $1.1354\ln n$ by applying the potential function technique. In addition, the author gives a nontrivial lower bound $1.0004609\ln n$ of performance guarantee of this algorithm. This lower bound, together with the matching bound of information content heuristic, confirms the fact information content heuristic is slightly better than setcover greedy algorithm in worst case.