Direction Matters: On Influence-Preserving Graph Summarization and Max-cut Principle for Directed Graphs
This addresses the need for efficient analysis and group-level feature extraction in directed graphs, which is useful for interventions in population behavior, but it is incremental as it builds on existing summarization approaches.
The paper tackles the problem of summarizing large directed graphs into smaller representations while preserving directed edge information, achieving this by minimizing reconstruction error with a Max-Cut principle and demonstrating accuracy and robustness in experiments.
Summarizing large-scaled directed graphs into small-scale representations is a useful but less studied problem setting. Conventional clustering approaches, which based on "Min-Cut"-style criteria, compress both the vertices and edges of the graph into the communities, that lead to a loss of directed edge information. On the other hand, compressing the vertices while preserving the directed edge information provides a way to learn the small-scale representation of a directed graph. The reconstruction error, which measures the edge information preserved by the summarized graph, can be used to learn such representation. Compared to the original graphs, the summarized graphs are easier to analyze and are capable of extracting group-level features which is useful for efficient interventions of population behavior. In this paper, we present a model, based on minimizing reconstruction error with non-negative constraints, which relates to a "Max-Cut" criterion that simultaneously identifies the compressed nodes and the directed compressed relations between these nodes. A multiplicative update algorithm with column-wise normalization is proposed. We further provide theoretical results on the identifiability of the model and on the convergence of the proposed algorithms. Experiments are conducted to demonstrate the accuracy and robustness of the proposed method.