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$.
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).
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