Graph Summarization via Node Grouping: A Spectral Algorithm

• URL: http://arxiv.org/abs/2211.04169v1
• Date: Tue, 8 Nov 2022 11:23:16 GMT
• Title: Graph Summarization via Node Grouping: A Spectral Algorithm
• Abstract summary: Graph summarization via node grouping is a popular method to build concise graph representations. In this paper, we reformulate the loss minimization problem for summarization into an equivalent integer problem. We show that SpecSumm efficiently produces high-quality summaries compared to state-of-the-art summarization algorithms.
• Score: 4.967873417059781
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Graph summarization via node grouping is a popular method to build concise graph representations by grouping nodes from the original graph into supernodes and encoding edges into superedges such that the loss of adjacency information is minimized. Such summaries have immense applications in large-scale graph analytics due to their small size and high query processing efficiency. In this paper, we reformulate the loss minimization problem for summarization into an equivalent integer maximization problem. By initially allowing relaxed (fractional) solutions for integer maximization, we analytically expose the underlying connections to the spectral properties of the adjacency matrix. Consequently, we design an algorithm called SpecSumm that consists of two phases. In the first phase, motivated by spectral graph theory, we apply k-means clustering on the k largest (in magnitude) eigenvectors of the adjacency matrix to assign nodes to supernodes. In the second phase, we propose a greedy heuristic that updates the initial assignment to further improve summary quality. Finally, via extensive experiments on 11 datasets, we show that SpecSumm efficiently produces high-quality summaries compared to state-of-the-art summarization algorithms and scales to graphs with millions of nodes.

Related papers

• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  We propose a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening.<n>We derive a faster variant NOPE*, which reduces O(dot d) interference evaluation to O(d) based on the local isotropy assumption.<n>Learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning.
  arXiv  Detail & Related papers  (2026-05-13T05:24:35Z)
• Sparse Graph Learning from Sparse Data via Fiedler Number Maximization [16.83442282933831]
  We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in RN, and the underlying distribution is unknown.<n>We incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective.<n> Simulation experiments show that Fiedler number robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.
  arXiv  Detail & Related papers  (2026-04-28T21:40:39Z)
• Dynamic Deep Graph Learning for Incomplete Multi-View Clustering with Masked Graph Reconstruction Loss [26.31060859315329]
  We propose a novel textbfDynamic Deep textbfGraph Learning for textbfIncomplete textbfMulti-textbfView textbfView textbfClustering with textbfMasked Graph Reconstruction Loss (DGIMVCM)<n>A graph convolutional embedding layer is then designed to extract primary features and refined dynamic view-specific graph structures, leveraging the global graph for imputation of missing views.
  arXiv  Detail & Related papers  (2025-11-14T11:26:38Z)
• Bounds on Perfect Node Classification: A Convex Graph Clustering Perspective [50.3088702686312]
  We present an analysis of the transductive node classification problem, where the underlying graph consists of communities that agree with the node labels and node features.<n>For node classification, we propose a novel optimization problem that incorporates the node-specific information in a spectral graph clustering framework.
  arXiv  Detail & Related papers  (2025-08-27T19:22:35Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification. By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
  arXiv  Detail & Related papers  (2023-08-12T02:47:57Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  gradient scarcity occurs when learning graphs by minimizing a loss on a subset of nodes causes edges between unlabelled nodes that are far from labelled ones to receive zero gradients. We give a precise mathematical characterization of this phenomenon, and prove it also emerges in bilevel optimization. To alleviate this issue, we study several solutions: we propose to resort to latent graph learning using a Graph-to-Graph model (G2G), graph regularization to impose a prior structure on the graph, or optimizing on a larger graph than the original one with a reduced diameter.
  arXiv  Detail & Related papers  (2023-03-24T12:37:43Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
  We propose a Graph Multiset Transformer (GMT) that captures the interaction between nodes according to their structural dependencies. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods on graph classification benchmarks.
  arXiv  Detail & Related papers  (2021-02-23T07:45:58Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling [31.812988573924674]
  In graph neural networks (GNNs), pooling operators compute local summaries of input graphs to capture their global properties. We propose the Node Decimation Pooling (NDP), a pooling operator for GNNs that generates coarser graphs while preserving the overall graph topology. NDP is more efficient compared to state-of-the-art graph pooling operators while reaching, at the same time, competitive performance on a significant variety of graph classification tasks.
  arXiv  Detail & Related papers  (2019-10-24T21:42:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.