# Meta-multigraph Search: Rethinking Meta-structure on Heterogeneous Information Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 53 references that are in the map.
- First posted on arXiv 23 Apr 2023.

## Builds on (most cited first, 30 of 34)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Efficient Neural Architecture Search via Parameter Sharing](https://mlsanity.com/paper/1802.03268/) (2018)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware](https://mlsanity.com/paper/1812.00332/) (2018)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Single Path One-Shot Neural Architecture Search with Uniform Sampling](https://mlsanity.com/paper/1904.00420/) (2019)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding](https://mlsanity.com/paper/2002.01680/) (2020)
- [PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search](https://mlsanity.com/paper/1907.05737/) (2019)
- [Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation](https://mlsanity.com/paper/1904.12760/) (2019)
- [Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks](https://mlsanity.com/paper/2112.14936/) (2021)
- [Multi-Stage Self-Supervised Learning for Graph Convolutional Networks on Graphs with Few Labels](https://mlsanity.com/paper/1902.11038/) (2019)
- [Graph Attention Multi-Layer Perceptron](https://mlsanity.com/paper/2206.04355/) (2022)
- [Auto-GNN: Neural Architecture Search of Graph Neural Networks](https://mlsanity.com/paper/1909.03184/) (2019)
- [Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training](https://mlsanity.com/paper/2104.09376/) (2021)
- [Search to aggregate neighborhood for graph neural network](https://mlsanity.com/paper/2104.06608/) (2021)
- [PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm](https://mlsanity.com/paper/2203.00638/) (2022)
- [ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse Coding](https://mlsanity.com/paper/2010.06176/) (2020)
- [DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2010.03250/) (2020)
- [Efficient Neural Architecture Search via Proximal Iterations](https://mlsanity.com/paper/1905.13577/) (2019)
- [Scalable Graph Neural Networks for Heterogeneous Graphs](https://mlsanity.com/paper/2011.09679/) (2020)
- [Towards Improving the Consistency, Efficiency, and Flexibility of Differentiable Neural Architecture Search](https://mlsanity.com/paper/2101.11342/) (2021)
- [Designing the Topology of Graph Neural Networks: A Novel Feature Fusion Perspective](https://mlsanity.com/paper/2112.14531/) (2021)

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

- [Disentangled Hyperbolic Representation Learning for Heterogeneous Graphs](https://mlsanity.com/paper/2406.10367/) (2024)

## Abstract (arXiv)

Meta-structures are widely used to define which subset of neighbors to aggregate information in heterogeneous information networks (HINs). In this work, we investigate existing meta-structures, including meta-path and meta-graph, and observe that they are initially designed manually with fixed patterns and hence are insufficient to encode various rich semantic information on diverse HINs. Through reflection on their limitation, we define a new concept called meta-multigraph as a more expressive and flexible generalization of meta-graph, and propose a stable differentiable search method to automatically optimize the meta-multigraph for specific HINs and tasks. As the flexibility of meta-multigraphs may propagate redundant messages, we further introduce a complex-to-concise (C2C) meta-multigraph that propagates messages from complex to concise along the depth of meta-multigraph. Moreover, we observe that the differentiable search typically suffers from unstable search and a significant gap between the meta-structures in search and evaluation. To this end, we propose a progressive search algorithm by implicitly narrowing the search space to improve search stability and reduce inconsistency. Extensive experiments are conducted on six medium-scale benchmark datasets and one large-scale benchmark dataset over two representative tasks, i.e., node classification and recommendation. Empirical results demonstrate that our search methods can automatically find expressive meta-multigraphs and C2C meta-multigraphs, enabling our model to outperform state-of-the-art heterogeneous graph neural networks.