47953: Business Technology Seminar (Fall 2013)

Methods and Algorithms for determining relevance in networks
Thursdays 1:00pm-4:50pm in GSIA 227 (starting Oct 24th)

Seminar Information

Seminar Description: In this seminar, we study a number of approaches for determining the relative importance of nodes in networks. The problem of relative relevance or importance in network and graphical data appears in a very broad spectrum of applications, such as: (1) Given a directed graph of web pages linking to other web pages, which web page is the most "relevant" given a certain keyword query? (2) Given a social network with undirected friendships between users: Which user in the network is the most "similar" to a chosen user? (3) Given an interaction network of users on eBay with a subset of nodes identified as fraudsters (labeled training data), which are the most likely other users that are fraudsters too based on common interaction patterns? (4) Given an electrical network and assuming independent failure of edges: which node from a chosen subset is the one that is most likely reachable (i.e. connected) to the source set ("source-terminal reliability")?

Our goal is to understand the connections between seemingly unconnected scenarios and algorithms by studying the workings, assumptions, and limitations of a few selected approached in depth, then trying to find common properties and differences. In doing so, our analysis and discussions will be guided by questions, such as:

• What is a good measure of "relevance" or "similarity?"
• When or why does one approach work better (what is the right metric) than another?
• What are some conditions under which one model can be transferred into another model?
• Why can some methods be evaluated in polynomial time while others are computationally hard?

Recommended Background Knowledge: The seminar is targeted towards PhD students with a good understanding of the following topics (or willingness to get up to speed during the seminar). We will, at time, read sections of these books:

1. Linear Algebra
   
   • [Lay 2011]: Lay: Linear algebra and its applications (book, 4th ed, 2011): excellent book!
2. Probability Theory
   
   • Bertsekas, Tsitsiklis: Introduction To Probability (book, 2nd ed, 2008): great book
3. Fundamentals of network theory
   
   • [Newman 2010]: Ch 6 and 7 of "Newman: Networks - An Introduction (book, 2010)"
4. Graphical models
   
   • [Bishop 2006]: Ch 8 of "Bishop: Pattern Recognition and Machine Learning (book, 2006)": Graphical models (free)
   • [Koller,F 2009]: Koller, Friedman: Probabilistic graphical models: principles and techniques (book, 2009)
   • [Murphy 2012]: Murphy: Machine Learning - a Probabilistic Perspective (book, 2012) (free)
5. Complexity theory
   
   • Ch 8 of "Dasgupta, Papadimitriou, Vazirani: Algorithms (book, 2006)": excellent free online book!
   • Ch 29 of "Jeff Erickson' Algorithm class": excellent free online class material

Instructor: Wolfgang Gatterbauer
Assistant Professor of Business Technologies, Tepper School of Business, CMU.
Courtesy Assistant Professor, School of Computer Science, CMU.
Email:
Office: Tepper 354
Office Hours: via email

Seminar Requirements

1. Presentations and in-class contributions (50%): We will study the workings and predictions of several different approaches. Everybody will read the papers upfront, and analyze the methods on suggested example graphs in the manner they find most appropriate (e.g., simulation in Matlab, or handwritten drawings). Students are given 20-30min at the beginning of each class to discuss their findings with another student that is randomly assigned by the instructor. Each team is expected to be able present their findings to the class (ideally on the overhead projector with handwritten slides). One pair of students are announced in the previous class and is in lead of the topic for each class. The lead team is expected to understand the paper more thoroughly then everybody else. Material from each students is handed in each class. Important: you do not need to hand in digitally prepared slides, often drawing by pen on paper together with your assigned partner is far more effective. Goal is to understand the paper, and to help others understand your insights, not to produce fancy slides. Thus come with your pen and lots of paper. We may also possibly use Baiboard for collaborative drawing in class by students and instructors (to be determined). Here are some guiding questions:

• What is the paper's setting? How does it differ from other papers read so far?
• What are the explicit and implicit assumptions made by the paper? Why this assumptions? Are they justified or not?
• What is the abstract problem the paper tries to solve? How does it differ from other papers read so far?
• What are the main strengths and weaknesses of this paper? What prevented the authors from addressing the weaknesses?
• What are the main technical contributions? Where does the paper fit in the related literature?
• How does the method work and what does it predict on a specific illustrative graph?
• How does the method generalize to other possible applications? Is there any relationship to empirical work? Are there testable implications?
• What are the conclusions?
• What did you learn from the paper?
• What are some possible follow-questions to be resolved?
• What are some other questions for additional discussion to which you may not know the answer yourself?

2. Written research proposal or small research project with presentation. (50%): Minimum 1000 words and 3 drawings, maximum 5000 words (no limit on drawings). Students will hand in and present their research proposals on the last day of class. The discussion will be very interactive, i.e. questions will be posed during presentation, not only after.

• 2a) Methods option (mainly targeted towards CS and ACO students)
  • Deals with a method / approach / algorithm that is motivated by or related to the class material.
  • Reviews, critiques and compares the relevant literature,
  • Proposes one or more pertinent and interesting research questions,
  • Communicates the (potential) contributions from studying these questions and their relevance both to research and practice,
  • Presents a possible approach, along with any developed model/method or analysis, and
  • Concludes with a summary and discussion of the main ideas and/or results and/or possible extensions.
  
  
• 2b) Applied option (mainly targeted towards more applied fields, e.g., Finance or OM)
  • Deals with a topic that is motivated by the students' discipline and data set of interest, yet still related to our class topic.
  • Motivates the relevance of the problem and reviews the current state-of the art
  • Adapts and compares one or several algorithms to this real-world application
  • Evaluates empirically how well the approach works, and why or why not.
  • Concludes with a summary and discussion of the main ideas and/or results and/or possible extensions.

Class schedule

Below is a tentative calendar. I may modify this list as we go along. Please see the date at the bottom of this page to learn if this post has been updated.

1. Oct 24: Random walks and variations (1a) Graph concepts, Variations of Shortest Paths, Random walks and PageRank Ch 2.6 of [Lay 2011]: The Leontief Input-Output model Ch 4.9 of [Lay 2011]: Markov Chains Ch 5.1 of [Lay 2011]: Eigenvalues Ch 6 of [Newman 2010]: Mathematics of Networks Ch 21 of "Manning, Raghavan, Schuetze: An introduction to information retrieval (book, 2008)": Link Analysis Optional: Ch 17.2.3 - 17.2.4 of [Murphy 2012]: Markov chains and PageRank Page, Brin, Motwani, Winograd: The PageRank Citation Ranking - Bringing Order to the Web (Technical Report, 1998) Kleinberg: Authoritative Sources in a Hyperlinked Environment (JACM, 1999) 2. Oct 31: From Random walks to Label Propagation (1b) Personalized PageRank, HITS and variations Ch 7 of [Newman 2010]: Measures and metrics Ch 21 of "Manning, Raghavan, Schuetze: An introduction to information retrieval (book, 2008)": Link Analysis Haveliwala, Kamvar, Jeh: An analytical comparison of approaches to personalizing PageRank (Technical Report, 2003) Optional: Berkhin - A Survey on PageRank Computing (Internet Mathematics, 2005) Cohen: Graph walks and graphical models (Technical Report, 2010) Altman, Tennenholtz: An Axiomatic Approach to Personalized Ranking Systems (JACM, 2010) (2) Label propagation Baluja et al.: Video Suggestion and Discovery for YouTube: Taking Random Walks Through the View Graph (WWW, 2008) Optional: Lao, Mitchell, Cohen - Random walk inference and learning in a large scale knowledge base (EMNLP, 2011) Bengio, Delalleau, Le Roux: Label Propagation and Quadratic Criterion (book Ch 11 of "Semi-Supervised Learning", 2006) Zhu, Ghahraman: Learning from Labeled and Unlabeled Data with Label Propagation (Technical Report, 2002) Zhou, Bousquet, Lal, Weston, Schoelkopf: Learning with local and global consistency (NIPS, 2003) 3. Nov 7: Belief Propagation and variations (3) Belief Propagation in Graphical Models Ch 22.2 of [Murphy 2012]: Loopy belief propagation Ch 8.4.4-8.4.7 of [Bishop 2006]: Sum-product algorithm to Loopy belief Propagation Optional: Weiss: Correctness of local probability propagation in graphical modes with loops (Neural Computation, 2000) Ch 4 of "Pearl: Probabilistic Reasoning in Intelligent Systems (1988)": Belief updating by network propagation Frey, MacKay: A Revolution: Belief Propagation in Graphs With Cycles (NIPS, 1997) Ch 4 of [Koller,F 2009] (4) Linearized Belief Propagation Koutra, Ke, Kang, Chau, Pao, Faloutsos: Unifying guilt-by-association approaches - theorems and fast algorithms (PKDD 2011) Gatterbauer, Guennemann, Koutra, Faloutsos: Linearized and Turbo Belief Propagation (working paper) 4. Nov 14: Network reliability and electrical networks / Structural Similarity (5) Laplacian matrix and Electrical networks Ch 6.14.1 of [Newman 2010]: Resistor networks Ch 1.1-1.3 of "Doyle, Snell: Random walks and electric networks (book, 1984, version 2000)" (6) Structural ("Regular") Similarity Ch 7.12.4 of [Newman 2010]: Regular Equivalence Jeh, Widom: SimRank - A Measure of Structural-Context Similarity (SIGKDD 2002) (7) Network reliability Wikipedia: Series-parallel graph Ch 2.1 of "Colbourn: The Combinatorics of Network Reliability (1987)": "Wheatstone bridge" Asthana, King, Gibbons, Roth: Predicting Protein Complex Membership Using Probabilistic Network Reliability (Genome Research, 2004) Detwiler, Gatterbauer, Louie, Suciu, Tarczy-Hornoch: Integrating and Ranking Uncertain Scientific Data (ICDE, 2009), Full technical report Optional: Provan, Ball: The complexity of counting cuts and of computing the probability that a graph is connected (SIAM J COMPUT, 1983) 5. Nov 21: Modeling the brain (8) Spreading activation Wikipedia: Spreading activation Wikipedia: Connectionism Crestani: Application of Spreading Activation Techniques in Information Retrieval (AI review 1997) Ziegler, Lausen: Spreading activation models for trust propagation (EC 2004) Optional: Anderson: A spreading activation theory of memory (Journal of Verbal Learning and Verbal Behavior, 1983) (9) Neural networks (Feed-forward networks → Backpropagation) Rumelhart, Hinton, Williams: Learning Internal Representations by Error Propagation (book chapter, 1986) McClelland: Training Hidden Units with Back Propagation (Ch 5 of Explorations in Parallel Distributed Processing, book draft, 2013) Tadeusiewcz: Principles of training multi-layer neural network using backpropagation (online, 2005) Ch 7 (Backpropagation) Rojas: Neural networks - a systematic introduction (book, 1996) Optional: Minsky, Papert: Perceptrons - An Introduction to Computational Geometry (book, 1987) (10) Deep belief networks Hinton, Osindero, Teh: A Fast Learning Algorithm for Deep Belief Nets (Neural computation, 2006) 6. Dec 5: From Graphs to Hypergraphs and Databases (11) Reliability → Boolean Functions → hypergraphs Gatterbauer, Suciu: Oblivious Bounds on the Probability of Boolean Functions (TODS 2013, to appear) (12) Hypergraphs & databases → probabilistic databases (query reliability vs. query dissociation) Suciu, Olteanu, Re, Koch: Probabilistic Databases - Synthesis Lectures on Data Management (book, 2012) Gatterbauer, Jha, Suciu: Dissociation and Propagation for Efficient Query Evaluation over Probabilistic Databases (MUD 2010) Gatterbauer, Suciu: Dissociation and Propagation for Efficient Query Evaluation over Probabilistic Databases (arXiv 2013) 7. Dec 12: Student presentations and comparative review

Updated on or after June 27, 2014
Contact: