Search

Hypergraphs are used in machine learning to model higher-order relationships in data. While spectral methods for graphs are well-established, spectral theory for hypergraphs remains an active area of research. In this paper, we use random walks to develop a spectral theory for hypergraphs with edge-dependent vertex weights: hypergraphs where every vertex $v$ has a weight $\gamma_e(v)$ for each incident hyperedge $e$ that describes the contribution of $v$ to the hyperedge $e$. We derive a random walk-based hypergraph Laplacian, and bound the mixing time of random walks on such hypergraphs. Moreover, we give conditions under which random walks on such hypergraphs are equivalent to random walks on graphs. As a corollary, we show that current machine learning methods that rely on Laplacians derived from random walks on hypergraphs with edge-independent vertex weights do not utilize higher-order relationships in the data. Finally, we demonstrate the advantages of hypergraphs with edge-dependent vertex weights on ranking applications using real-world datasets., Comment: Accepted to ICML 2019

Recent studies suggest that social media usage -- while linked to an increased diversity of information and perspectives for users -- has exacerbated user polarization on many issues. A popular theory for this phenomenon centers on the concept of "filter bubbles": by automatically recommending content that a user is likely to agree with, social network algorithms create echo chambers of similarly-minded users that would not have arisen otherwise. However, while echo chambers have been observed in real-world networks, the evidence for filter bubbles is largely post-hoc. In this work, we develop a mathematical framework to study the filter bubble theory. We modify the classic Friedkin-Johnsen opinion dynamics model by introducing another actor, the network administrator, who filters content for users by making small changes to the edge weights of a social network (for example, adjusting a news feed algorithm to change the level of interaction between users). On real-world networks from Reddit and Twitter, we show that when the network administrator is incentivized to reduce disagreement among users, even relatively small edge changes can result in the formation of echo chambers in the network and increase user polarization. We theoretically support this observed sensitivity of social networks to outside intervention by analyzing synthetic graphs generated from the stochastic block model. Finally, we show that a slight modification to the incentives of the network administrator can mitigate the filter bubble effect while minimally affecting the administrator's target objective, user disagreement., Comment: Accepted to KDD WISDOM19 workshop