Belief Propagation for Maximum Coverage on Weighted Bipartite Graph and Application to Text Summarization
This work addresses text summarization for NLP applications, but it is incremental as it extends an existing method to weighted graphs.
The authors tackled text summarization by framing it as a maximum coverage problem on weighted bipartite graphs, generalizing a belief propagation algorithm from unweighted to weighted graphs, and achieved better performance than greedy algorithms in some settings.
We study text summarization from the viewpoint of maximum coverage problem. In graph theory, the task of text summarization is regarded as maximum coverage problem on bipartite graph with weighted nodes. In recent study, belief-propagation based algorithm for maximum coverage on unweighted graph was proposed using the idea of statistical mechanics. We generalize it to weighted graph for text summarization. Then we apply our algorithm to weighted biregular random graph for verification of maximum coverage performance. We also apply it to bipartite graph representing real document in open text dataset, and check the performance of text summarization. As a result, our algorithm exhibits better performance than greedy-type algorithm in some setting of text summarization.