Interpretable graph learning that scales to millions of nodes
HARMONIA: Interpretable Graph Learning through Mixtures of Neural Bases
Artificial IntelligenceMachine Learning
Summary
Graphs help us understand relationships, but explaining predictions from graph data can be slow or unclear. The authors introduce a method called HARMONIA that breaks down predictions into clear feature-by-feature parts while handling very large graphs efficiently. Their approach uses a clever way to group similar features and track many-step connections without heavy computation. This lets machines explain their guesses better without slowing down or losing accuracy.
What this means in practice
- •For data engineers: Build graph-based prediction systems that explain which features and connections drive each prediction at scale.
- •For social network analysts: Analyze influence paths and feature impacts in large social networks with interpretable results that handle millions of users.
Authors
Quan D. Bui, Nguyen Do, An Nguyen Dang, Huyen Nguyen, Nhu Duc Minh Nguyen, My T. Thai
Abstract
Existing interpretable graph additive models still face limitations in either computational scalability or modeling flexibility. In terms of structural modeling, previous approaches either face quadratic scaling costs or sacrifice explicit source-to-target contribution decomposition. In terms of feature components, they rely either on per-feature neural networks or on single shared bases with limited feature specialization. We address both problems by introducing HARMONIA: Interpretable Graph Learning through Mixtures of Neural Bases, an interpretable-by-design framework. For feature modeling, HARMONIA introduces a Mixture of Neural Bases (MoNB), which routes features to specialized basis experts, enabling parameter sharing without sacrificing feature-specific specialization. For structural modeling, HARMONIA uses Relative Random Walk Probabilities (RRWP) to capture multi-hop and multi-path relationships, and proposes Sparse RRWP Aggregation (SRA) to compute these interactions through sparse graph propagation without quadratic pairwise complexity. HARMONIA retains a simple additive form in which predictions decompose into feature responses modulated by structural influence. Empirically, HARMONIA achieves stronger explanation recovery than existing interpretable graph baselines while maintaining competitive predictive performance and scaling to graphs with millions of nodes. These results show that interpretable graph learning can remain both faithful and scalable without sacrificing predictive effectiveness.