Graph neural networks (GNNs) have achieved great success on various graph tasks. However, recent studies have re-vealed that GNNs are vulnerable to adversarial attacks, including topology modifications and feature perturbations. Regardless of the fruitful progress, existing attackers require node labels and GNN parameters to optimize a bi-level problem, or cannot cover both topology modifications and feature perturbations, which are not practical, efficient, or effective. In this paper, we propose a black-box attacker PEEGA, which is restricted to access node features and graph topology for practicability. Specifically, we propose to measure the negative impact of various adversarial attacks from the perspective of node representations, thereby we formulate a single-level problem that can be efficiently solved. Furthermore, we observe that existing attackers tend to blur the context of nodes through adding edges between nodes with different labels. As a result, GNNs are unable to recognize nodes. Based on this observation, we propose a GNN defender GNAT, which incorporates three augmented graphs, i.e., a topology graph, a feature graph, and an ego graph, to make the context of nodes more distinguishable. Extensive experiments on three real-world datasets demonstrate the effectiveness and efficiency of our proposed attacker, despite the fact that we do not access node labels and GNN parameters. Moreover, the effectiveness and efficiency of our proposed defender are also validated by substantial experiments.

Heterogeneous information networks (HINs) are usually used to model information systems with multi-type objects and relations. In contrast, graphs that have a single type of nodes and edges, are often called homogeneous graphs. Measuring similarities among objects is an important task in data mining applications, such as web search, link prediction, and clustering. Currently, several similarity measures are defined for HINs. Most of these measures are based on meta-paths, which show sequences of node classes and edge types along the paths between two nodes. However, meta-paths, which are often designed by domain experts, are hard to enumerate and choose w.r.t. the quality of similarity scores. This makes using existing similarity measures in real applications difficult. To address this problem, we extend SimRank, a well-known similarity measure on homogeneous graphs, to HINs, by introducing the concept of the decay graph. The newly proposed similarity measure is called HowSim, which has the property of being meta-path free, and capturing the structural and semantic similarity simultaneously. The generality and effectiveness of HowSim, and the efficiency of our proposed algorithms for computing HowSim scores, are demonstrated by extensive experiments.

Measuring similarities among different nodes is important in graph analysis tasks, such as link prediction, and recommendation. Among different similarity measures, SimRank is one of the most popular and promising ones, and has received a lot of research attention. While most current studies focus on single-pair, single-source/top-k, and all-pairs SimRank computation, few of them have studied finding similar pairs given a set of node pairs, which has attractive applications in personalized search and recommendation tasks. In this paper, we present Carmo, an efficient algorithm for retrieving the top-k similarities from an arbitrary set of pairs. In addition, we introduce two types of indexes to boost the efficiency of Carmo: one is hub-based, the other is tree-based. We show the effectiveness and efficiency of our proposed methods by extensive experiments.

Learning network embeddings has attracted growing attention in recent years. However, most of the existing methods focus on homogeneous networks, which cannot capture the important type information in heterogeneous networks. To address this problem, in this paper, we propose TransN, a novel multi-view network embedding framework for heterogeneous networks. Compared with the existing methods, TransN is an unsupervised framework which does not require node labels or user-specified meta-paths as inputs. In addition, TransN is capable of handling more general types of heterogeneous networks than the previous works. Specifically, in our framework TransN, we propose a novel algorithm to capture the proximity information inside each single view. Moreover, to transfer the learned information across views, we propose an algorithm to translate the node embeddings between different views based on the dual-learning mechanism, which can both capture the complex relations between node embeddings in different views, and preserve the proximity information inside each view during the translation. We conduct extensive experiments on real-world heterogeneous networks, whose results demonstrate that the node embeddings generated by TransN outperform those of competitors in various network mining tasks.

Heterogeneous information networks (HINs) are usually used to model information systems with multi-type objects and relations. Measuring the similarity among objects is an important task in data mining applications. Currently, several similarity measures are defined for HIN. Most of these measures are based on meta-paths, which show sequences of node classes and edge types along the paths between two nodes. However, meta-paths, which are often designed by domain experts, are hard to enumerate and choose w.r.t. the quality of the similarity scores. This makes the existing similarity measures difficult to use in real applications. To address this problem, we extend SimRank, a well-known similarity measure for homogeneous graphs, to HINs, by introducing the concept of decay graph. The newly proposed relevance measure is called HowSim, which has the property of being meta-path free, and capturing the structural and semantic similarity simultaneously. The generality and effectiveness of HowSim, are demonstrated by extensive experiments.

Nowadays, most openly available knowledge bases (KBs) are incomplete, since they are not synchronized with the emerging facts happening in the real world. Therefore, knowledge base population (KBP) from external data sources, which extracts knowledge from unstructured text to populate KBs, becomes a vital task. Recent research proposes two types of solutions that partially address this problem, but the performance of these solutions is limited. The first solution, dynamic KB construction from unstructured text, requires specifications of which predicates are of interest to the KB, which needs preliminary setups and is not suitable for an in-time population scenario. The second solution, Open Information Extraction (Open IE) from unstructured text, has limitations in producing facts that can be directly linked to the target KB without redundancy and ambiguity. In this paper, we present an end-to-end system, KBPearl, for KBP, which takes an incomplete KB and a large corpus of text as input, to (1) organize the noisy extraction from Open IE into canonicalized facts; and (2) populate the KB by joint entity and relation linking, utilizing the context knowledge of the facts and the side information inferred from the source text. We demonstrate the effectiveness and efficiency of KBPearl against the state-of-the-art techniques, through extensive experiments on real-world datasets.

In this paper, we propose an efficient hierarchical index, G*-tree, to optimize spatial queries on road networks. Most existing graph indexes can only support one kind of query, and thus we need to build multiple indexes on a road network to handle various kinds of spatial queries, which is inefficient and unscalable for real-world applications. To address the problem, a recent study proposes G-tree to support multiple types of spatial queries on road networks within one framework. However, the assembly-based method on G-tree is not efficient enough to handle spatial queries when vertices, which are close in a road network, are distant in G-tree. To address the inefficiency problem of G-tree, in this paper, we propose a novel index structure on road networks, namely G*-tree, whose key idea is to build shortcuts between selected leaf nodes. Based on G*-tree, we propose three shortcut-based algorithms to answer distance queries, k-nearest neighbor queries and range queries, respectively, which are more efficient than the existing assembly-based algorithms on G-tree. Moreover, we propose a shortcut selection algorithm to optimize the performance of spatial queries on G*-tree. We conduct extensive experiments to compare our G*-tree and the state-of-the-art indexing methods on various large-scale road networks, where the results demonstrate that our G*-tree has better efficiency and scalability than the competitors to handle spatial queries.

Graph similarity search is a common and fundamental operation in graph databases. One of the most popular graph similarity measures is the Graph Edit Distance (GED) mainly because of its broad applicability and high interpretability. Despite its prevalence, exact GED computation is proved to be NP-hard, which could result in unsatisfactory computational efficiency on large graphs. However, exactly accurate search results are usually unnecessary for real-world applications especially when the responsiveness is far more important than the accuracy. Thus, in this paper, we propose a novel probabilistic approach to efficiently estimate GED, which is further leveraged for the graph similarity search. Specifically, we first take branches as elementary structures in graphs, and introduce a novel graph similarity measure by comparing branches between graphs, i.e., Graph Branch Distance (GBD), which can be efficiently calculated in polynomial time. Then, we formulate the relationship between GED and GBD by considering branch variations as the result ascribed to graph edit operations, and model this process by probabilistic approaches. By applying our model, the GED between any two graphs can be efficiently estimated by their GBD, and these estimations are finally utilized in the graph similarity search. Extensive experiments show that our approach has better accuracy, efficiency and scalability than other comparable methods in the graph similarity search over real and synthetic data sets.

Nowadays, the prevalence of sharing tourist photos to online communities has created an increasing demand for mining discriminative architecture aspects from historic landmarks. Some previous researches have demonstrated that topic models could discover discriminative features represented by meaningful visual-topics. However, they seldom exploited the indicative function of geo-tags and the hierarchy in architecture characteristics. In order to utilize this information, we proposed a semi-supervised hierarchical topic modeling approach (namely, shTM). In our approach, every image could be represented by a probability distribution over selected geo-related visual-topics from a partly randomized topic tree. We evaluated our approach on a real-world dataset with over 26 thousand geo-informative photos from Flickr. Experiments show that shTM topics could reveal more discriminative aspects of a specific architecture than other well-known image features, such as HOG and SIFT, on the tasks of automatic photo categorization and geographical information retrieval.