Susan L. Epstein
(Hunter College and The Graduate Center of The City University of New York)
Beyond Two: Discovering Complex Relationships in Real-world Problems

Real-world problems and human perceptions about them are considerably richer and more challenging than pairwise relationships suggest. This talk explores the shortcomings of a traditional focus on pairwise similarity metrics, and shows how sets of similar objects better support incisive reasoning and intelligent behavior.

In three diverse domains, a new algorithm detects subgraphs of size greater than two that support particular goals. The first domain is constraint satisfaction problems, where binary graphs represent the degree to which variables mutually restrict one another. Here, the algorithm discovers particularly difficult subproblems, directs initial resources to them, demonstrably accelerates search, and clarifies the nature of the problem for human users. The second domain is protein-protein interaction (PPI) networks, where binary graphs represent known interactions between proteins. Here, the algorithm discovers sets of genes that interact heavily with one another and suggests avenues of investigation for human researchers. The third domain is item recommendation, where sets of binary graphs represent multiple similarities among movies. Here, the algorithm discovers subsets that support recommendations for a prospective viewer.

In each case, facets of similarity are explored and controlled to support reasoning and develop expertise.