Convolutional Signal Propagation: A Simple Scalable Algorithm for Hypergraphs
This provides a simple baseline for hypergraph node classification and retrieval, addressing a gap in methods for more complex structures beyond standard graphs.
The paper tackles the problem of learning on complex structures like bipartite graphs (hypergraphs) by proposing Convolutional Signal Propagation (CSP), a non-parametric, scalable method that achieves competitive performance in retrieval and classification tasks while maintaining low computational complexity.
Last decade has seen the emergence of numerous methods for learning on graphs, particularly Graph Neural Networks (GNNs). These methods, however, are often not directly applicable to more complex structures like bipartite graphs (equivalent to hypergraphs), which represent interactions among two entity types (e.g. a user liking a movie). This paper proposes Convolutional Signal Propagation (CSP), a non-parametric simple and scalable method that natively operates on bipartite graphs (hypergraphs) and can be implemented with just a few lines of code. After defining CSP, we demonstrate its relationship with well-established methods like label propagation, Naive Bayes, and Hypergraph Convolutional Networks. We evaluate CSP against several reference methods on real-world datasets from multiple domains, focusing on retrieval and classification tasks. Our results show that CSP offers competitive performance while maintaining low computational complexity, making it an ideal first choice as a baseline for hypergraph node classification and retrieval. Moreover, despite operating on hypergraphs, CSP achieves good results in tasks typically not associated with hypergraphs, such as natural language processing.