KDD/UAI 2005 Conference Review Session

Query incentive networks
by Jon Kleinberg and Prabhakar Raghavan
Jure Leskovec

We propose a notion of incentive networks, modeling online settings in which multiple participant in a network help each other find information. Within this general setting, we study query incentive networks: users seeking information can pose queries, together with incentives for answering them, that are propagated along the paths in the network. In such systems, it is a fundamental question to understand how much incentive is needed in order for a node to achieve a reasonably probability of extracting an answer. We analyze strategic behavior in such networks and under a simple model of networks show that the Nash equilibrium for participants' strategies exhibits an unexpected threshold phenomenon. Classically studied criticality for branching process is centered around the region where the branching parameter is 1, we show in contrast that strategic interaction in incentive propagation exhibits critical behavior when the branching parameter is 2.

Structured Region Graphs: Morphing EP into GBP
by M Welling, T Minka and Y W Teh
Anna Goldenberg

GBP and EP are two successful algorithms for approximate probabilistic inference, which are based on different approximation strategies. An open problem in both algorithms has been how to choose an appropriate approximation structure. This work introduces ``structured region graphs,'' a formalism which marries these two strategies, reveals a deep connection between them, and suggests how to choose good approximation structures. In this formalism, each region has an internal structure which defines an exponential family, whose sufficient statistics must be matched by the parent region. Reduction operators on these structures allow conversion between EP and GBP free energies. Thus it is revealed that all EP approximations on discrete variables are special cases of GBP, and conversely that some well-known GBP approximations, such as overlapping squares, are special cases of EP. Furthermore, region graphs derived from EP have a number of good structural properties, including maxent-normality and overall counting number of one. The result is a convenient framework for producing high-quality approximations with a user-adjustable level of complexity.

Back to the Main Page