Graph is a generic model of various networks in real-world applications. And, graph embedding aims to represent nodes (edges or graphs) as low-dimensional vectors which can be fed into machine learning algorithms for downstream graph analysis tasks. However, existing random walk-based node embedding methods often map some nodes with (dis)similar local structures to (near) far vectors. To overcome this issue, this paper proposes to implement node embedding by constructing a context graph via a new defined ripple distance over ripple vectors, whose components are the hitting times of fully condensed neighborhoods and thus characterize their structures as pure quantities. The distance is able to capture the (dis)similarities of nodes’ local neighborhood structures and satisfies the triangular inequality. The neighbors of each node in the context graph are defined via the ripple distance, which makes the short random walks from a given node over the context graph only visit its similar nodes in the original graph. This property guarantees that the proposed method, named as $$\mathsf {ripple2vec}$$ , is able to map (dis)similar nodes to (far) near vectors. Experimental results on real datasets, where labels are mainly related to nodes’ local structures, show that the results of $$\mathsf {ripple2vec}$$ behave better than those of state-of-the-art methods, in node clustering and node classification, and are competitive to other methods in link prediction.
28 March 2022 in Computational Intelligence and Neuroscience
Travel time estimation (TTE) is widely applied for ride dispatching, ride-hailing, and route navigation. Even for a given trajectory, the travel time is affected by many spatial-temporal factors, including static ones such as distance, road type, and so on and dynamic ones such as speed, traffic condition, and so on. Challenges of accurate estimation lie in proper representation of these spatial-temporal factors and more importantly capturing the complex relationship among them for TTE. To tackle such challenges, we present a framework based on the fact that the travel time of each road segment is affected by its adjacent segments. It features a graph convolutional neural network and a recurrent neural network for basic TTE for each road segment and a graph attention network for the relation to estimations on the adjacent road segments. Finally, a multitask learning model is proposed for the travel time of the entire given path and that for each road segment. Experimental results on real taxi trajectory datasets of two cities show that the percentage estimation error of the new approach is well controlled at 13.91% and the proposed method outperforms three state-of-the-art methods significantly.
This paper revisits set containment join (SCJ) problem, which uses the subset relationship (i.e., $$\subseteq$$ ) as condition to join set-valued attributes of two relations and has many fundamental applications in commercial and scientific fields. Existing in-memory algorithms for SCJ are either signature-based or prefix-tree-based. The former incurs high CPU cost because of the enumeration of signatures, while the latter incurs high space cost because of the storage of prefix trees. This paper proposes a new adaptive parameter-free in-memory algorithm, named as frequency-hashjoin or $${\mathsf {FreshJoin}}$$ in short, to evaluate SCJ efficiently. $${\mathsf {FreshJoin}}$$ builds a flat index on-the-fly to record three kinds of signatures (i.e., two least frequent elements and a hash signature whose length is determined adaptively by the frequencies of elements in the universe set). The index consists of two sparse inverted indices and two arrays which record hash signatures of all sets in each relation. The index is well organized such that $${\mathsf {FreshJoin}}$$ can avoid enumerating hash signatures. The rationality of this design is explained. And, the time and space cost of the proposed algorithm, which provide a rule to choose $${\mathsf {FreshJoin}}$$ from existing algorithms, are analyzed. Experiments on 16 real-life datasets show that $${\mathsf {FreshJoin}}$$ usually reduces more than 50% of space cost while remains as competitive as the state-of-the-art algorithms in running time.
With the extensive application and in-depth study of Location-based Social Networks (LBSNs), more and more businesses are utilizing the new social platform to promote their products and services. In this paper, we explore an important technique that can help business to promote their locations by distributing items with business information or the leaflets of the business at some locations. In order to maximize the benefit of location promotion, this paper formally defines it as a location influence scope maximization problem on an location-based social network, i.e., given a target business and an LBSN, the problem is to find a set of K locations where the business distributes small promotional gifts or leaflets on, such that people who visited these locations can successfully propagate the advertisement information to most other locations for attracting most people to visit the target location. The existing related researches neglect location influences studies on location promotion (outdoor marketing). And it is more challenging to derive the influence between locations and the spatial influence scope of each location, since location influence depends on users mobility and the target location. In this paper, we provide a new approach (called as LoP) to exploit influence between locations for location promotion. First, LoP incrementally mines correlations between locations to instruct the location-location graph (LLG). Then, LoP predicts each location’s influence on others and its influence scope based on betweenness centrality. Finally, we provide the lazy algorithm to efficiently find a top-K set of influential locations for the business. Extensive experiments based on two real LBSN datasets have verified the superior effectiveness of our proposed method in term of location promotion.