InfoGain Wavelets: Furthering the Design of Graph Diffusion Wavelets

David R. Johnson, Smita Krishnaswamy, Michael Perlmutter

Abstract

Diffusion wavelets extract information from graph signals at different scales of resolution by utilizing graph diffusion operators raised to various powers, known as diffusion scales. Traditionally, these scales are chosen to be dyadic integers, $2^j$. Here, we propose a novel, unsupervised method for selecting the diffusion scales based on ideas from information theory. We then show that our method can be incorporated into wavelet-based GNNs, which are modeled after the geometric scattering transform, via graph classification experiments.

Benchmark Results

Tested on 3 datasets

Tables show presented results in global context (best 3 papers + GCN + MLP).

TU Dortmund

MUTAG

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	MSH-GNN GNN global	0.9910 ±0.0030	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
2	ID-GNN+BEC Hyb global	0.9830 ±0.0360	Depth-Adaptive Graph Neural Networks via Learnable Bakry-Émery Curvature
3	SupCosine Hyb global	0.9830 ±0.0250	Supervised Contrastive Learning with Structure Inference for Graph Classification
39	GIN GNN global	0.9330 ±0.0290	ProtGNN: Towards Self-Explaining Graph Neural Networks
403	MLP code ↗ Trad global	0.8660 ±0.0495	Breaking the Limits of Message Passing Graph Neural Networks code ↗
430	LS-InfoGain Hyb ★ proposed	0.8567 ±0.1004	This paper
431	LS-InfoGain Wavelets-16-drop ★ proposed	0.8567 ±0.1004	This paper
465	LEGS-16-original-ATTN-FCN GNN baseline	0.8460 ±0.0613	This paper
556	LEGS-16-subset baseline	0.8240 ±0.0912	This paper
568	LEGS Hyb baseline	0.8193 ±0.0999	This paper
569	LEGS-16-full baseline	0.8193 ±0.0999	This paper
608	LS-dyadic Hyb baseline	0.8035 ±0.0959	This paper
610	LS-dyadic-16-full baseline	0.8035 ±0.0959	This paper
676	LS-dyadic-subset baseline	0.7728 ±0.1850	This paper

NCI1

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	WL-MLP GT global	0.9954	1-WL Expressiveness Is (Almost) All You Need
2	GIN GNN global	0.9934	1-WL Expressiveness Is (Almost) All You Need
3	GCN GNN global	0.9727	1-WL Expressiveness Is (Almost) All You Need
131	GraphSAGE code ↗ GNN global	0.8200 ±0.0100	Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings code ↗
340	LS-InfoGain Hyb ★ proposed	0.7747 ±0.0242	This paper
341	LS-InfoGain Wavelets-16-drop ★ proposed	0.7747 ±0.0242	This paper
376	LS-dyadic Hyb baseline	0.7642 ±0.0279	This paper
377	LS-dyadic-16-full baseline	0.7642 ±0.0279	This paper
432	LEGS-16-original-RBF GNN baseline	0.7426 ±0.0153	This paper
486	LEGS Hyb baseline	0.6973 ±0.0194	This paper
487	LEGS-16-full baseline	0.6973 ±0.0194	This paper

PROTEINS

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	MSH-GNN GNN global	0.9410 ±0.0330	Multi-Scale Harmonic Encoding for Feature-Wise Graph Message Passing
2	GRDL GNN global	0.8260 ±0.0120	Graph Classification via Reference Distribution Learning: Theory and Practice
3	GMN code ↗ Hyb global	0.8225	Memory-Based Graph Networks code ↗
32	GIN GNN global	0.7880 ±0.0410	Permutation-Invariant graph partitioning: How graph neural networks capture structural …
149	MLP Trad global	0.7600 ±0.0320	Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors
171	LS-dyadic Hyb baseline	0.7575 ±0.0350	This paper
173	LS-dyadic-16-full baseline	0.7575 ±0.0350	This paper
270	LS-InfoGain Hyb ★ proposed	0.7485 ±0.0389	This paper
271	LS-InfoGain-16-drop ★ proposed	0.7485 ±0.0389	This paper
295	LEGS Hyb baseline	0.7440 ±0.0419	This paper
296	LEGS-16-full baseline	0.7440 ±0.0419	This paper
441	LEGS-16-original-FCN GNN baseline	0.7106 ±0.0317	This paper

SOTA performance (not significantly different from the best) Proposed method (this paper) Baseline / comparison (this paper) Global context (other papers)