{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72873"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72873","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Walking forward and backward: towards graph-based searching and mining","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.\"","abstract_html":""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."","abstract_has_math":false,"creators":["Fang, Yuan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Chang, Kevin C.","Han, Jiawei","Zhai, ChengXiang","Krishnaswamy, Shonali"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-01-21T19:49:04Z","date_published":"2015-01-21T19:49:04Z","updated_at":"2026-07-22T22:26:07Z","subjects":["Graph","searching and mining","random walk","semi-supervised learning","smoothness"],"languages":["en"],"rights":["Copyright 2014 Yuan Fang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/72873","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Chang, Kevin C.","Han, Jiawei","Zhai, ChengXiang","Krishnaswamy, Shonali"]},{"key":"dc:creator","label":"Author","values":["Fang, Yuan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-01-21T19:49:04Z","2014-12","2015-01-21"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph","searching and mining","random walk","semi-supervised learning","smoothness"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Yuan Fang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72873"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["\"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.\"","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-09-03T16:12:56Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Fang_Yuan.pdf: 3041597 bytes, checksum: 15ccf154ae022d2c9f5b3ecce9239361 (MD5)","Made available in DSpace on 2015-01-21T19:49:04Z (GMT). No. of bitstreams: 1 Yuan_Fang.pdf: 3041597 bytes, checksum: 15ccf154ae022d2c9f5b3ecce9239361 (MD5)"]},{"key":"dc:title","label":"Title","values":["Walking forward and backward: towards graph-based searching and mining"]}]}],"canonical_facts":{"dc:contributor":["Chang, Kevin C.","Han, Jiawei","Zhai, ChengXiang","Krishnaswamy, Shonali"],"dc:creator":["Fang, Yuan"],"dc:date":["2015-01-21T19:49:04Z","2014-12","2015-01-21"],"dc:description":["\"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.\"","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-09-03T16:12:56Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Fang_Yuan.pdf: 3041597 bytes, checksum: 15ccf154ae022d2c9f5b3ecce9239361 (MD5)","Made available in DSpace on 2015-01-21T19:49:04Z (GMT). No. of bitstreams: 1 Yuan_Fang.pdf: 3041597 bytes, checksum: 15ccf154ae022d2c9f5b3ecce9239361 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/72873"],"dc:language":["en"],"dc:rights":["Copyright 2014 Yuan Fang"],"dc:subject":["Graph","searching and mining","random walk","semi-supervised learning","smoothness"],"dc:title":["Walking forward and backward: towards graph-based searching and mining"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:07Z"}