Vertex collocation profiles: theory, computation, and results

A Supervised Link Prediction Method Using Optimized Vertex Collocation Profile

Classical link prediction methods mainly utilize vertex information and topological structure to predict missing links in networks. However, accessing vertex information in real-world networks, such as social networks, is still challenging. Moreover, link prediction methods based on topological structure are usually heuristic, and mainly consider common neighbors, vertex degrees and paths, which cannot fully represent the topology context. In recent years, network embedding models have shown efficiency for link prediction, but they lack interpretability. To address these issues, this paper proposes a novel link prediction method based on an optimized vertex collocation profile (OVCP). First, the 7-subgraph topology was proposed to represent the topology context of vertexes. Second, any 7-subgraph can be converted into a unique address by OVCP, and then we obtained the interpretable feature vectors of vertexes. Third, the classification model with OVCP features was used to predict links, and the overlapping community detection algorithm was employed to divide a network into multiple small communities, which can greatly reduce the complexity of our method. Experimental results demonstrate that the proposed method can achieve a promising performance compared with traditional link prediction methods, and has better interpretability than network-embedding-based methods.

Estimation of Graphlet Counts in Massive Networks

Graphlets are induced subgraphs of a large network and are important for understanding and modeling complex networks. Despite their practical importance, graphlets have been severely limited to applications and domains with relatively small graphs. Most previous work has focused on exact algorithms; however, it is often too expensive to compute graphlets exactly in massive networks with billions of edges, and finding an approximate count is usually sufficient for many applications. In this paper, we propose an unbiased graphlet estimation framework that is: (a) fast with large speedups compared to the state of the art; (b) parallel with nearly linear speedups; (c) accurate with less than 1% relative error; (d) scalable and space efficient for massive networks with billions of edges; and (e) effective for a variety of real-world settings as well as estimating global and local graphlet statistics (e.g., counts). On 300 networks from 20 domains, we obtain <1% relative error for all graphlets. This is vastly more accurate than the existing methods while using less data. Moreover, it takes a few seconds on billion edge graphs (as opposed to days/weeks). These are by far the largest graphlet computations to date.

Multiple Structure-View Learning for Graph Classification

Many applications involve objects containing structure and rich content information, each describing different feature aspects of the object. Graph learning and classification is a common tool for handling such objects. To date, existing graph classification has been limited to the single-graph setting with each object being represented as one graph from a single structure-view. This inherently limits its use to the classification of complicated objects containing complex structures and uncertain labels. In this paper, we advance graph classification to handle multigraph learning for complicated objects from multiple structure views, where each object is represented as a bag containing several graphs and the label is only available for each graph bag but not individual graphs inside the bag. To learn such graph classification models, we propose a multistructure-view bag constrained learning (MSVBL) algorithm, which aims to explore substructure features across multiple structure views for learning. By enabling joint regularization across multiple structure views and enforcing labeling constraints at the bag and graph levels, MSVBL is able to discover the most effective substructure features across all structure views. Experiments and comparisons on real-world data sets validate and demonstrate the superior performance of MSVBL in representing complicated objects as multigraph for classification, e.g., MSVBL outperforms the state-of-the-art multiview graph classification and multiview multi-instance learning approaches.