Powerset Convolutional Neural Networks

Chris Wendler, Markus Püschel, Dan Alistarh

TL;DR

Powerset Convolutional Neural Networks (PCNs) bring the power of deep learning to "set functions"—data where values are assigned to every possible subset of a group. By defining novel mathematical "shifts" based on set operations, the authors create a principled convolutional framework that outperforms standard graph-based methods on tasks like identifying submodularity and classifying hypergraph structures.

What Problem Does This Paper Address?

Deep learning has mastered regular grids (images) and irregular graphs (social networks). However, a vast category of data exists as set functions, where a signal is indexed by the powerset of a finite set. Examples include combinatorial auctions (valuing bundles of goods), sensor placement optimization, and cooperative game theory (valuing coalitions of players).

Until now, researchers usually handled this data in one of two ways: treating it as a flat vector for a Multi-Layer Perceptron (MLP) or viewing it as a "hypercube graph" to apply Graph Convolutional Networks (GCNs). Both approaches have flaws. MLPs ignore the inherent structure of sets, and GCNs use a single "omnidirectional" shift (the Laplacian) that treats all set elements the same. This paper fills the gap by providing a native convolutional architecture designed specifically for the algebraic structure of powersets.

Methods

The authors derive their architecture using Algebraic Signal Processing (ASP). The core innovation lies in how they define "convolution" for sets:

  1. Powerset Shifts: Instead of shifting a pixel to the right, they define shifts based on set operations. For a subset $Q$, the shift $T_Q$ moves a signal from set $A$ to $A \setminus Q$. Crucially, this provides a unique shift for every element in the ground set, allowing the network to learn "directional" features.
  2. Convolutional Layers: A powerset convolution is defined as a linear, shift-equivariant function. In practice, this means the filter "slides" across the powerset lattice, responding to specific patterns of set inclusions.
  3. Fourier Analysis: To make computation efficient, the authors use the Powerset Fourier Transform (a variant of the Walsh-Hadamard Transform). This allows them to perform convolutions as point-wise multiplications in the frequency domain.
  4. Powerset Pooling: They introduce a novel pooling layer that reduces the size of the ground set (e.g., merging two elements into one), effectively downsampling the powerset while preserving its mathematical properties.
Powerset CNN Architecture

Datasets

The authors evaluated their model on both synthetic and real-world data:

  • Synthetic Tasks:
    • Spectral Patterns: Classifying signals based on their frequency components.
  • $k$-junta Classification: Identifying functions that only depend on a small subset ($k$) of the total elements.
  • Submodularity: Distinguishing between submodular functions (which exhibit "diminishing returns") and perturbed versions.
  • Real-World Hypergraphs: Using 19 datasets (like DBLP co-authorship and congressional bills), they created tasks to identify the origin of a sub-hypergraph (Domain Classification) and determine if a set of vertices forms a "closed" hyperedge (Simplicial Closure).

Key Insights and Ideas

  • Directionality Matters: Unlike Graph CNNs, which are "blind" to which specific neighbor they are looking at, Powerset CNNs have $n$ basic shifts (one for each element). This allows the model to distinguish between adding "Element A" vs. "Element B" to a set.
  • Non-Invertible Shifts: Set shifts are not always invertible (you can't always "undo" a set difference perfectly). This means that a pattern "detected" by a filter looks different depending on where it appears in the powerset lattice—a fundamental departure from the translation-invariance of image CNNs.
  • The Hypercube Connection: The authors show that standard Hypercube GCNs are actually a restricted, "symmetric" subset of Powerset CNNs. By relaxing these symmetry constraints, PCNs gain significantly more expressive power.

Key Results

  • Synthetic Superiority: On the "Patterns" task, the PCN achieved 88.5% accuracy, dwarfing the best GCN baseline (65.5%) and the MLP (46.8%).
  • Hypergraph Performance: On real-world data, PCNs were generally the top performers. In the "DOM6" domain classification task, the PCN reached 73.5% accuracy, outperforming the Laplacian-based GCN (71.7%).
  • Pooling Efficiency: The proposed powerset pooling successfully reduced computational complexity with minimal impact on accuracy, proving that hierarchical feature extraction works for sets just as it does for images.
Experimental Results Table

Limitations and Future Work

  • The Curse of Dimensionality: The primary limitation is scale. Because a powerset grows at a rate of $2^n$, the current methodology is only feasible for ground sets up to roughly $n=30$ elements. Beyond this, the data objects become too large to fit in memory.
  • Sparsity: Many real-world set functions are sparse (most subsets have a value of zero). The authors suggest that future work should focus on "sparse powerset convolutions" to handle much larger ground sets.
  • Data Scarcity: Unlike the world of Computer Vision, there are currently few large-scale, labeled "set function" datasets. The authors hope their framework encourages the community to curate more diverse data in this domain.

Summary updated

Abstract

We present a novel class of convolutional neural networks (CNNs) for set functions, i.e., data indexed with the powerset of a finite set. The convolutions are derived as linear, shift-equivariant functions for various notions of shifts on set functions. The framework is fundamentally different from graph convolutions based on the Laplacian, as it provides not one but several basic shifts, one for each element in the ground set. Prototypical experiments with several set function classification tasks on synthetic datasets and on datasets derived from real-world hypergraphs demonstrate the potential of our new powerset CNNs.
BibTeX
@inproceedings{wendler2019powerset,
  author = {Chris Wendler and Markus Püschel and Dan Alistarh},
  title = {{Powerset Convolutional Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=Cmg3tsaFtvLX},
}
Figure