Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Model

Tianxi Cai, Dong Xia, Luwan Zhang, Doudou Zhou

Abstract

Network analysis has been a powerful tool to unveil relationships and interactions among a large number of objects. Yet its effectiveness in accurately identifying important node-node interactions is challenged by the rapidly growing network size, with data being collected at an unprecedented granularity and scale. Common wisdom to overcome such high dimensionality is collapsing nodes into smaller groups and conducting connectivity analysis on the group level. Dividing efforts into two phases inevitably opens a gap in consistency and drives down efficiency. Consensus learning emerges as a new normal for common knowledge discovery with multiple data sources available. To this end, this paper features developing a unified framework of simultaneous grouping and connectivity analysis by combining multiple data sources. The algorithm also guarantees a statistically optimal estimator.

Introduction

Network analysis is a cornerstone of modern data science, utilized to map complex systems ranging from protein-protein interactions to social networks. However, as these networks scale to include millions of nodes, researchers face two primary hurdles. First, high dimensionality often leads to redundancy, where multiple nodes represent nearly identical entities (e.g., "heart disease" versus "coronary artery disease"). Traditional workflows address this by grouping nodes first and analyzing connectivity second, but this sequential approach often results in information loss and inconsistent results.

Second, multi-view heterogeneity complicates the synthesis of data from disparate sources. In medical informatics, for instance, different hospital systems may record the same clinical concepts but with varying frequencies, biases, and noise levels. Simply averaging these sources ignores their unique characteristics, leading to a "blurry" or biased consensus. This paper introduces the multi-view sparse low-rank block model (msLBM), a unified framework designed to learn a consensus knowledge graph by simultaneously grouping nodes and inferring connectivity across multiple heterogeneous data sources.

The msLBM Framework

The core of the proposed approach is the msLBM framework, which models observed data from each source as a composite of three distinct elements:

  1. A Shared Low-Rank Component: This represents the "consensus" knowledge graph. It utilizes a Low-Rank Block Model (LBM), which generalizes the traditional Stochastic Block Model (SBM). A critical feature of the LBM is that it decouples the number of groups ($K$) from the latent embedding dimension ($r$). This allows the model to accommodate many clusters (high $K$) even when the underlying relationship space is relatively small (low $r$), a common scenario in medical data where thousands of synonymous terms may map to a few core biological pathways.
  2. A View-Specific Sparse Bias ($\Theta$): This term captures patterns unique to a specific data source—such as a hospital's unique patient demographic—ensuring these biases do not contaminate the global consensus.
  3. Noise ($E$): This accounts for standard random error inherent in data collection.

By explicitly modeling the heterogeneity as a feature rather than a nuisance, msLBM "de-biases" individual views to extract a cleaner, more accurate global truth.

Methodology and Scalability

To solve the optimization problem presented by msLBM, the authors developed an alternating minimization algorithm. This algorithm iteratively updates node groupings, node-wise importance (heterogeneity), and the sparse bias terms. Recognizing the computational demands of modern medical informatics, the researchers also introduced a "fast and inexact" version of the update process. This ensures the model can scale to massive datasets without sacrificing the statistical optimality of the estimator.

Experimental Validation

The researchers evaluated the msLBM framework using both synthetic simulations and a massive real-world medical dataset. The primary application involved $n = 7,217$ clinical concepts extracted from three major Electronic Health Record (EHR) sources:

  • Partners Healthcare System (PHS): 10 million clinical notes from 62,000 patients.
  • Stanford Hospital: 20 million clinical notes.
  • MIMIC-III: A publicly available database of intensive care unit (ICU) notes.

Performance was benchmarked against existing methods such as Sum of Adjacency Matrices (SAM) and Multiple Adjacency Spectral Embedding (MASE), as well as human-annotated semantic similarity scores and established medical relationship databases (e.g., "May Cause," "May Treat").

Key Results

The msLBM framework demonstrated significant improvements over baseline methods in both accuracy and clinical relevance:

  • Superior Accuracy: In simulations, msLBM consistently achieved lower mis-clustering errors than SAM or MASE, particularly as the number of groups ($K$) increased.
  • Alignment with Human Knowledge: On the EHR data, msLBM achieved a Spearman correlation of 0.635 with human-annotated relatedness scores. This significantly outperformed the best single-source model (0.567) and other multi-view aggregation methods.
  • Clinical Discovery: The model successfully reconstructed the progression of Coronary Artery Disease (CAD), accurately mapping the trajectory from Hyperlipidemia to Angina and Myocardial Infarction. It also correctly identified relevant medications, such as Beta-blockers and Nitrates, within the learned network structure.

Limitations and Future Work

While msLBM represents a significant step forward, several challenges remain. The alternating minimization process, even in its "fast" iteration, is computationally expensive for graphs with millions of nodes. Furthermore, the model's success relies on the assumption that biases are sparse and the consensus is low-rank; dense, complex biases in a single source may still pose challenges for separation. Finally, the current framework focuses on symmetric relationship matrices. Extending msLBM to accommodate asymmetric, directed graphs is a promising avenue for future research.

Conclusion

The multi-view sparse low-rank block model provides a robust, statistically grounded framework for extracting consensus knowledge from high-dimensional, heterogeneous data. By integrating grouping and connectivity analysis into a single step, msLBM avoids the pitfalls of sequential processing and offers a clearer window into the complex relationships hidden within large-scale datasets.

Summary updated

Abstract

Network analysis has been a powerful tool to unveil relationships and interactions among a large number of objects. Yet its effectiveness in accurately identifying important node-node interactions is challenged by the rapidly growing network size, with data being collected at an unprecedented granularity and scale. Common wisdom to overcome such high dimensionality is collapsing nodes into smaller groups and conducting connectivity analysis on the group level. Dividing efforts into two phases inevitably opens a gap in consistency and drives down efficiency. Consensus learning emerges as a new normal for common knowledge discovery with multiple data sources available. To this end, this paper features developing a unified framework of simultaneous grouping and connectivity analysis by combining multiple data sources. The algorithm also guarantees a statistically optimal estimator.
BibTeX
@misc{cai2022consensus,
  author = {Tianxi Cai and Dong Xia and Luwan Zhang and Doudou Zhou},
  title = {{Consensus Knowledge Graph Learning via Multi-view Sparse Low Rank Block Model}},
  year = {2022},
  eprint = {2209.13762},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.13762},
}

Loading related content...

Figure