Powerset Convolutional Neural Networks

Chris Wendler, Dan Alistarh, Markus Püschel

Introduction

Deep learning has achieved remarkable success on data structured as regular grids (images) or graphs. However, many critical mathematical and real-world objects are best represented as set functions: mappings that assign a real value to every possible subset of a finite collection. Examples include cooperative games, sensor placement problems, and hypergraph interactions.

Historically, researchers have approached set functions by either treating the $2^{|N|}$ possible subsets as a flat vector in a Multi-Layer Perceptron (MLP)—ignoring the inherent lattice structure—or by treating the powerset as a hypercube graph for Graph Convolutional Networks (GCNs). While GCNs are an improvement, they are "omnidirectional," treating all element connections identically and losing the distinct identity of individual set elements. This paper introduces Powerset Convolutional Neural Networks (PCNs), a framework that respects the unique algebraic structure of powersets through multi-directional shifts.

Methodology: The Powerset Convolutional Architecture

The core innovation of PCNs is the Powerset Convolution, derived from Algebraic Signal Processing (ASP). Unlike a standard image CNN with simple spatial shifts, or a GCN with a single Laplacian shift, a PCN defines $n$ distinct basic shifts—one for each element in the ground set $N$.

The PCN architecture showing successive convolution and pooling layers on the powerset lattice.

Key components of the architecture include:

  • Multi-Directional Shifts: By having $n$ shifts, the network can learn "directional" features specific to individual elements, capturing more nuanced structural information than a standard GCN.
  • Shift Equivariance: The convolutions are designed to be shift-equivariant, ensuring that set operations (like removing an element) result in predictable changes in the output.
  • Localized Filters: The authors utilize "$k$-localized" filters. For instance, a 1-localized filter considers a subset and its immediate neighbors in the lattice (sets differing by only one element).
  • Powerset Pooling: To manage dimensionality, a pooling layer merges elements of the ground set, effectively shrinking the powerset lattice while preserving its fundamental structure.
  • Spectral Computation: For efficiency, convolutions are computed in the frequency domain using a specialized Powerset Fourier Transform, a variant of the Walsh-Hadamard Transform.

Empirical Evaluation

The authors evaluated PCNs against MLPs and GCN baselines across synthetic tasks (like submodularity detection and $k$-junta classification) and real-world hypergraph datasets (domain classification and simplicial closure).

Performance comparison of PCN variants against MLP and GCN baselines across synthetic and real-world datasets.

As shown in the results table, PCNs consistently outperform traditional models. In the "Spectral Patterns" synthetic task, the PCN achieved 88.5% accuracy, significantly higher than the best-performing GCN (65.5%). On real-world hypergraph domain classification (DOM4/DOM6), PCN variants (particularly those using average pooling) achieved the highest accuracies, demonstrating their ability to extract structural "fingerprints" from complex relational data.

Discussion and Future Outlook

A key insight from this work is the "N-Directional" advantage: standard GCNs on a hypercube are essentially a restricted subset of PCNs where filters for every element are forced to be identical. By relaxing this constraint, PCNs capture significantly more detail. Furthermore, because powerset shifts are non-invertible, the patterns a filter detects change depending on the subset's position in the lattice, a unique property not found in traditional CNNs.

Despite their power, PCNs face a significant challenge: The Exponential Curse. Because a ground set of size $n$ results in $2^n$ data points, the architecture is currently limited to $n \approx 30$. Future research will likely focus on developing sparse PCNs to handle larger ground sets by only computing values for "interesting" subsets, and expanding the availability of labeled set-function datasets to further train these specialized architectures.

Summary updated

BibTeX
@inproceedings{wendler2019powerset,
  author = {Chris Wendler and Dan Alistarh and Markus Püschel},
  title = {{Powerset Convolutional Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=Cmg3tsaFtvLX},
}

Loading related content...

Figure