Learning Relation Networks for Relational RetrievalThesis Proposal, Ni LaoMar 2, 2011Committee:William W. Cohen, (chair) Teruko MitamuraGeoffrey J. Gordon C Lee Giles (Pennsylvania State University)3/2/2011 1C. Lee Giles, (Pennsylvania State University) OutlineOutline• Introduction– Tasks & motivation –Thesis goal & expected contributionsThesis goal & expected contributions– Compare to existing approaches• Our Prior Work( )–Path Ranking Algo rithm (Lao & Cohen, ECML 2010)– Efficient inference (Lao & Cohen, KDD 2010)• Proposed Model Efficiency Extensionsp y– Sparse gradient estimation– Cost sensitive parameter regularization•Proposed Model Complexity Extensions•Proposed Model Complexity Extensions– Virtual Relations– Path concatenation– Graph structure learning–Relation networks• Work in Progress–Reading recommendation (Lao & Cohen ISMB)3/2/2011 2Reading recommendation (Lao & Cohen, ISMB)– Link prediction with an ontology (Lao et al., EMNLP)Relational Retrieval ProblemsRelational Retrieval ProblemsDt f ti l/ d ti tk b•Data of many retrieval/recommendation tasks can be represented as labeled directed graphs, e.g. scientific literature–Typed nodes: documents, terms, metadata– Labeled edges: citation, authorOf, datePublished• Can support a family of typed proximity queries– ad hoc retrieval: termsÆ documents– Citation recommendation: paper Æ papers• Which combination of these relations is important in answering the queries?g q33/2/2011Biology Literature DataBiology Literature Data•FlyminegraphCit1267531Physical/Genetic•FlyminegraphPublication126813Author233229Write679,903Gene516416Protein414824689,812Cite 1,267,531yinteractions1,352,820Transcribe293,285126,813233,229516,416414,824Bioentity1,785,626Downstream/UptreamYear58Journal1801Title Terms1022232,060,275• TasksBioentity5,823,37658 1,801before102,223– Gene recommendation: user, yearÆgene– Reference recommendation: title words,yearÆpaper–Venue recommendation: genes, title wordsÆjournal– Expert‐finding: title words, genesÆauthor– Reading recommendation: userÆpaper43/2/2011Biology Literature DataBiology Literature DataEltt i fdi dti•Example strategies for reading recommendation12Write CitedByauthor paper paper⎯⎯⎯→⎯⎯⎯→11 22Read WrittenBy Writeauthor paper author paper⎯⎯⎯→⎯⎯⎯⎯→⎯⎯⎯→• Random walk with restart can be used for inference• How to discover and combine different retrieval str ategies?53/2/2011Knowledgebase DataKnowledgebase Data•Graph representation of a knowledgebase•Graph representation of a knowledgebase– entities and concepts as nodes, and relations among them as edges– NELL@CMU (Never‐Ending Language Learner) has over 242K beliefsegAthletePlaysSport(agassi tennis) Generalizations(redmond city)–e.g. AthletePlaysSport(agassi,tennis), Generalizations(redmond,city)• Expand knowledgebase by link predictiongiven a node X and an relation type R what are the nodes in the graph which–given a node X and an relation type R, what are the nodes in the graph which should have relation R with X?– e.g. ?Y: AthletePlaysSport(agassi,Y)1Pl F Pl112PlaysFor PlaysFor Playsathlete team athlete sport−⎯⎯⎯⎯→ ⎯⎯⎯⎯→⎯⎯⎯→1PlaysForPlaysathlete team sport⎯⎯⎯⎯→⎯⎯⎯→• Random walk with restart can be used for inference• How to discov er and combine different retrieval strategies?3/2/2011 6OutlineOutline• Introduction– Tasks & motivation –Thesis goal & expected contributionsThesis goal & expected contributions– Compare to existing approaches• Our Prior Work( )–Path Ranking Algo rithm (Lao & Cohen, ECML 2010)– Efficient inference (Lao & Cohen, KDD 2010)• Proposed Model Efficiency Extensionsp y– Sparse gradient estimation– Cost sensitive parameter regularization•Proposed Model Complexity Extensions•Proposed Model Complexity Extensions– Virtual Relations– Path concatenation– Graph structure learning–Relation networks• Work in Progress–Reading recommendation (Lao & Cohen ISMB)3/2/2011 7Reading recommendation (Lao & Cohen, ISMB)– Link prediction with an ontology (Lao et al., EMNLP)Thesis GoalThesis Goal • Explore different ways of constructing the random walk models so that complex retrieval str ategies on graph can be encoded• We also develop algo rithms that can efficiently di d tth tt idiscover and ex ecute these strategies3/2/2011 8Our Prior WorkOur Prior Workrecommendation tasks in biology literature domainhard to manually design retrievaldiscover retrieval schemes from user feedbackstructured data with complex schemadesign retrieval schemesexpensive tofrom user feedback (Lao & Cohen, ECML2010)approximated expensive to execute complex retrieval schemesapp o a edrandom walk strategies(Lao & Cohen, KDD 2010)93/2/2011Expected ContributionsExpected ContributionsModel Complexitygraph structure learningrelation networkpath concatenationvirtual relationspopular entity expertsindependent extensionsEfficiencypath ranking algorithmquery independent pathspopular entity expertsefficient inferencesparse gradient estimationcost sensitive parameter regularizationrecommendation tasks in biology domainrecommendation tasks in computer science domaingcomputer science domainInformation extraction/integrations tasks with ontology or parsed text corporaboxed items are our prior work3/2/2011 10ApplicationOutlineOutline• Introduction– Tasks & motivation –Thesis goal & expected contributionsThesis goal & expected contributions– Compare to existing approaches• Our Prior Work( )–Path Ranking Algo rithm (Lao & Cohen, ECML 2010)– Efficient inference (Lao & Cohen, KDD 2010)• Proposed Model Efficiency Extensionsp y– Sparse gradient estimation– Cost sensitive parameter regularization•Proposed Model Complexity Extensions•Proposed Model Complexity Extensions– Virtual Relations– Path concatenation– Graph structure learning–Relation networks• Work in Progress–Reading recommendation (Lao & Cohen ISMB)3/2/2011 11Reading recommendation (Lao & Cohen, ISMB)– Link prediction with an ontology (Lao et al., EMNLP)Random Walks with Restart (RWR)•RWR is a commonly used similarity measure for proximity betweenRandom Walks with Restart (RWR)RWR is a commonly used similarity measure for proximity between query and target nodes– topic‐sensitive Pagera nk (Haveliwala, 2002) – personalized Pagerank (Jeh &. Widom, 2003)Obj