Product Graph Learning From Multi-Attribute Graph Signals with Inter-Layer Coupling

Chenyue Zhang, Yiran He, Hoi-To WaiICASSP 2023 · OpenReview

TL;DR

This paper introduces a new framework for learning the structure of complex, multi-layered networks (product graphs) from multi-attribute data. They propose a novel graph filter model that accounts for inter-layer coupling and develop two spectral methods, one exact (using Nearest Kronecker Product Decomposition) and one simplified (using unfolding), to infer network topology and identify important nodes. Their findings show that the exact method is robust to strong inter-layer coupling, which can degrade the simplified approach.

What Problem Does This Paper Address?

Many real-world systems, like social networks or biological interactions, are not isolated but rather consist of multiple interconnected layers. Data observed on these systems often has multiple attributes, meaning each node can have different types of information associated with it. Traditional graph learning methods typically focus on single-layer networks and single-attribute data, failing to capture the rich interactions within and across these layers. This paper addresses the challenge of learning the underlying structure of these "product graphs" from multi-attribute signals, which is crucial for understanding complex systems and developing accurate inference algorithms.

Methods

The authors propose a bivariate polynomial graph filter to model multi-attribute graph signals living on a product graph. This filter captures interactions across both the "physical" graph (representing entities) and the "coupling" graph (representing attributes or layers).

For inferring the network structure, they adapt existing spectral methods. The core idea is that the eigenvectors of the graph signal's covariance matrix can be related to the eigenvectors of the physical and coupling graphs. They propose two solutions for estimating these eigenvectors:

  1. Nearest Kronecker Product Decomposition (NKD): This method leverages the mathematical property that Kronecker products can be decomposed. It's presented as an exact solution under certain assumptions, particularly robust to strong inter-layer coupling.
  2. Simplified Solution via Unfolding: This approach involves reshaping the multi-attribute data into matrices that represent layers or nodes. While simpler, the paper shows it can be sensitive to strong inter-layer coupling.

Datasets

The paper uses synthetic data generated according to their proposed model for evaluating both topology reconstruction and central node detection. They also evaluate their method on a real-world dataset: US Senate Rollcalls data from the 113th-116th Congress. For this dataset, they use Non-negative Matrix Factorization (NMF) to derive the number of topics (layers) before applying their product graph learning framework.

Key Insights and Ideas

  • Product graphs are essential for modeling complex systems: The paper highlights that many real-world networks are inherently multi-layered, and a product graph model is a more faithful representation than single-layer or flattened approaches.
  • Inter-layer coupling is a critical factor: The strength of connections between layers significantly impacts the performance of graph learning algorithms. Strong coupling can be detrimental to simpler methods.
  • NKD offers robustness: The Nearest Kronecker Product Decomposition method emerges as a powerful tool for inferring network structure, especially when inter-layer coupling is strong, providing an exact solution under mild conditions.
  • Spectral methods can be adapted: By relating the covariance of multi-attribute graph signals to the underlying graph structures, spectral methods can be effectively adapted for product graph learning.

Key Results

  • Topology Reconstruction: The proposed "NKD" method consistently outperforms "Unfold," "PGL," and "Flatten" methods in reconstructing the graph topology, achieving higher F1 scores across various sample and graph sizes, and is less sensitive to the inter-layer coupling parameter ($\gamma_1$). For instance, in Figure 2, NKD maintains high F1 scores even when $\gamma_1 = 0.01$, while other methods degrade.
  • Central Node Detection: The NKD-based algorithm demonstrates lower error rates in identifying central nodes compared to the "Unfold" method, particularly in scenarios with strong inter-layer coupling ($\gamma_1 = 0.01$). This is attributed to the covariance matrices having less repeated eigenvalues, leading to better eigenvector estimation with fewer samples.
  • Real-world application: On the US Senate Rollcalls data, their method successfully infers a product graph structure, identifying distinct clusters for Republican and Democratic states and revealing strong connections between topics like "circuit judges" and "fiscal."

Limitations and Future Work

  • Identifiability conditions: While the paper proposes methods, further analysis of the sampling complexity of Algorithm 1 and the conditions for identifiability under various scenarios (e.g., with noise) could be beneficial.
  • Layer-wise vs. Node-wise Unfolding: The paper notes that the simplified unfolding method's performance is tied to the separability of the graph filter. Future work could explore how different unfolding strategies impact sampling complexity and identifiability in more general cases.
  • Generalizing the model: The current work focuses on homogeneous layers. Extending the framework to handle heterogeneous layers in product graphs would be a valuable next step.

Summary updated

Abstract

This paper considers learning a product graph from multi-attribute graph signals. Our work is motivated by the widespread presence of multilayer networks that feature interactions within and across graph layers. Focusing on a product graph setting with homogeneous layers, we propose a bivariate polynomial graph filter model. We then consider the topology inference problems thru adapting existing spectral methods. We propose two solutions for the required spectral estimation step: a simplified solution via unfolding the multiattribute data into matrices, and an exact solution via nearest Kro-necker product decomposition (NKD). Interestingly, we show that strong inter-layer coupling can degrade the performance of the unfolding solution while the NKD solution is robust to inter-layer coupling effects. Numerical experiments show efficacy of our methods.
BibTeX
@inproceedings{zhang2023product,
  author = {Chenyue Zhang and Yiran He and Hoi-To Wai},
  title = {{Product Graph Learning From Multi-Attribute Graph Signals with Inter-Layer Coupling}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  url = {https://openreview.net/forum?id=SujDQMWpB0},
}
Figure