University of Illinois Urbana-Champaign

Walking forward and backward: towards graph-based searching and mining

Fang, Yuan

Content Files
Yuan_Fang.pdf

Permalink

https://hdl.handle.net/2142/72873

Description

Title
Walking forward and backward: towards graph-based searching and mining
Author(s)
Fang, Yuan
Issue Date
2015-01-21
Director of Research (if dissertation) or Advisor (if thesis)
Chang, Kevin C.
Doctoral Committee Chair(s)
Chang, Kevin C.
Committee Member(s)
  • Han, Jiawei
  • Zhai, ChengXiang
  • Krishnaswamy, Shonali
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Date of Ingest
2015-01-21T19:49:04Z
Keyword(s)
  • Graph
  • searching and mining
  • random walk
  • semi-supervised learning
  • smoothness
Abstract
"Graphs are powerful vehicles to represent data objects that are interconnecting or interacting with each other. We explore random walks on various kinds of graph to address different searching and mining scenarios. This dissertation focuses on two symmetric forms of random walk called the forward walk and backward walk, which can be applied to enrich three key tasks in searching and mining, namely, extraction, ranking and classification, in novel ways. More specifically, we enhance extraction with the metrics of probabilistic precision and recall, ranking with the senses of importance and specificity, and classification with heterogeneous contexts in terms of relationship type and confidence level. We further study the underpinning principle of random walks on a graph, which is often known as the smoothness assumption. We argue that smoothness is a pointwise property and requires probabilistic modeling. Thus, we propose a new framework to define pointwise smoothness probabilistically on a graph, which unifies two different ""modes"" of smoothness corresponding to the forward and backward random walks, respectively. Finally, our graph-based random walk solutions have consistently demonstrated promising empirical results for a wide range of searching and mining applications."
Graduation Semester
2014-12
Permalink
http://hdl.handle.net/2142/72873
Copyright and License Information
Copyright 2014 Yuan Fang

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science