# Discovering Representative Attribute-stars via Minimum Description Length

arXiv: https://arxiv.org/abs/2204.12704 · HTML: https://mlsanity.com/paper/2204.12704/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 46 references that are in the map.
- First posted on arXiv 27 Apr 2022.

## Builds on (most cited first, 10 of 10)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks](https://mlsanity.com/paper/1704.06803/) (2017)
- [Discrete-time Temporal Network Embedding via Implicit Hierarchical Learning in Hyperbolic Space](https://mlsanity.com/paper/2107.03767/) (2021)
- [Learning on Attribute-Missing Graphs](https://mlsanity.com/paper/2011.01623/) (2020)
- [FeatureNorm: L2 Feature Normalization for Dynamic Graph Embedding](https://mlsanity.com/paper/2103.00164/) (2021)
- [Graph Summarization Methods and Applications: A Survey](https://mlsanity.com/paper/1612.04883/) (2016)
- [Keeping it Short and Simple: Summarising Complex Event Sequences with Multivariate Patterns](https://mlsanity.com/paper/1512.07056/) (2015)

## Built on by (most cited first, 5 of 5)

- [Hypformer: Exploring Efficient Transformer Fully in Hyperbolic Space](https://mlsanity.com/paper/2407.01290/) (2024)
- [kHGCN: Tree-likeness Modeling via Continuous and Discrete Curvature Learning](https://mlsanity.com/paper/2212.01793/) (2022)
- [Mitigating Semantic Confusion from Hostile Neighborhood for Graph Active Learning](https://mlsanity.com/paper/2308.08823/) (2023)
- [Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation](https://mlsanity.com/paper/2505.20992/) (2025)
- [GLADMamba: Unsupervised Graph-Level Anomaly Detection Powered by Selective State Space Model](https://mlsanity.com/paper/2503.17903/) (2025)

## Abstract (arXiv)

Graphs are a popular data type found in many domains. Numerous techniques have been proposed to find interesting patterns in graphs to help understand the data and support decision-making. However, there are generally two limitations that hinder their practical use: (1) they have multiple parameters that are hard to set but greatly influence results, (2) and they generally focus on identifying complex subgraphs while ignoring relationships between attributes of nodes.Graphs are a popular data type found in many domains. Numerous techniques have been proposed to find interesting patterns in graphs to help understand the data and support decision-making. However, there are generally two limitations that hinder their practical use: (1) they have multiple parameters that are hard to set but greatly influence results, (2) and they generally focus on identifying complex subgraphs while ignoring relationships between attributes of nodes. To address these problems, we propose a parameter-free algorithm named CSPM (Compressing Star Pattern Miner) which identifies star-shaped patterns that indicate strong correlations among attributes via the concept of conditional entropy and the minimum description length principle. Experiments performed on several benchmark datasets show that CSPM reveals insightful and interpretable patterns and is efficient in runtime. Moreover, quantitative evaluations on two real-world applications show that CSPM has broad applications as it successfully boosts the accuracy of graph attribute completion models by up to 30.68% and uncovers important patterns in telecommunication alarm data.