Direction Matters: On Influence-Preserving Graph Summarization and Max-Cut Principle for Directed Graphs.
Neural Comput
; 33(8): 2128-2162, 2021 Jul 26.
Article
en En
| MEDLINE
| ID: mdl-34310677
ABSTRACT
Summarizing large-scale directed graphs into small-scale representations is a useful but less-studied problem setting. Conventional clustering approaches, based on Min-Cut-style criteria, compress both the vertices and edges of the graph into the communities, which 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, useful for efficient interventions of population behavior. In this letter, we present a model, based on minimizing reconstruction error with nonnegative 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 the convergence of the proposed algorithms. Experiments are conducted to demonstrate the accuracy and robustness of the proposed method.
Texto completo:
1
Colección:
01-internacional
Banco de datos:
MEDLINE
Tipo de estudio:
Prognostic_studies
Idioma:
En
Revista:
Neural Comput
Asunto de la revista:
INFORMATICA MEDICA
Año:
2021
Tipo del documento:
Article
País de afiliación:
Reino Unido