ON THE PREDICTIVE MODELING OF ATTRIBUTED GRAPHS

Abstract

In various domains, such as information retrieval, earth science, remote sensing and social network, vast amounts of data can be viewed as attributed graphs as they are associated with attributes which describe the property of data and structure which reflects the inter-dependency among variables in the data. Given the broad coverage and the unique representation of attributed graphs, many studies with a focus on predictive modeling have been conducted. For example, node prediction aims at predicting the attributes of nodes; link prediction aims at predicting the graph structure; graph prediction aims at predicting the attributes from the entire graph. To provide better predictive modeling, we need to gain deep insights from the principle elements of the attributed graph. In this thesis, we explore answers to three open questions: (1) how to discover the structure of the graph efficiently? (2) how to find a compact and lossless representation of the attributes of the graph? (3) how to exploit the temporal contexts exhibited in the graph? For structure learning, we first propose a structure learning method which is capable of modeling the nonlinear relationship between attributes and target variables. The method is more effective than alternative approaches which are without nonlinear modeling or structure learning on the task of graph regression. It however suffers from the high computational cost brought from the structure learning. To address this limitation, we then propose a conditional dependency network which can discover the graph structure in a distributed manner. The experimental results suggest that this method is much more efficient than other methods while being comparable in terms of effectiveness. For representation learning, we introduced a Structure-Aware Intrinsic Representation Learning model. Different from existing methods which only focus on learning the compact representation of the target space of the attributed graph. Our method can jointly learn lower dimensional embeddings of the target space and feature space via structure-aware graph abstraction and feature-aware target embedding learning. The results indicate that the embedding produced from the proposed method is better than the ones from alternative state-of-the-art embedding learning methods across all experimental settings. For temporal modeling, we introduced a time-aware neural attentive model to capture the temporal dynamics exhibited in session-based news recommendation, in which the user's sequential behaviors are attributed graphs with chain structure and temporal contexts as attributes. The unique temporal dynamics specific to news include: readers' interests shift over time, readers comment irregularly on articles, and articles are perishable items with limited lifespans. The result demonstrates the effectiveness of our method against a number of state-of-the-art methods on several real-world news datasets.