Methods that combine evidence from several sources using belief functions can say more than probabilities can. They can express "this point is in cluster A or B, but I can't tell which", and they can express "this view tells me nothing at all". Multi-view learning, where each sample is described by several feature sets such as image descriptors, text, and tags, is the natural place to use that ability. Current neural evidential methods discard it for cost reasons. They allow only single-class beliefs plus one "total ignorance" mass, because combining beliefs over arbitrary subsets of classes is #P-hard. Meanwhile, the multi-view clustering methods that actually scale to 100,000 samples are fully deterministic and cannot tell when a view is untrustworthy or missing.
This note proposes a way to get both. Scalable multi-view clustering already builds trees of anchor points, coarse-to-fine summaries of the data. If each view's beliefs are placed only on the class subsets defined by its own tree, then within a view any two subsets are either nested or disjoint. Dempster's combination rule is polynomial-time on such nested-or-disjoint evidence. When different views' trees disagree, a known 2-SAT test detects it and a known merging algorithm repairs it. Those algorithms have never been tried on real data, so the proposal is also an empirical validation of them: how often real views produce compatible trees, how much repair is needed, and whether the extra expressiveness improves clustering under missing and corrupted views.
Core Claim
The claim is that compound-hypothesis belief fusion is cheap on real multi-view data when the focal sets come from anchor hierarchies. A focal set is a subset of clusters that receives nonzero belief mass. We expect the cost of exact fusion to be governed not by the $2^c$ subsets of $c$ clusters but by the size of the intersection closure of the views' trees. The intersection closure is the set of all distinct subsets generated by intersecting tree nodes across views. If the union of the trees is laminar, meaning every pair of subsets is nested or disjoint, the closure is at most the total number of tree nodes. Exact combination then costs time linear in that number per sample and $O(n)$ overall.
The second part of the claim concerns accuracy. Mass on intermediate tree nodes, together with vacuous evidence for missing views, should beat the singleton-plus-ignorance restriction specifically in the incomplete and corrupted regimes where deterministic anchor methods have nothing to say about reliability. In a vacuous belief assignment, all mass goes to the full set of clusters.
Grounding in Prior Work
Several papers motivate the gap from the evidential side. Trusted Multi-View Classification turns each view's network output into Dirichlet evidence and fuses the views with a reduced Dempster rule, so that uncertain views are downweighted per sample. Its successor, Trusted Multi-View Classification with Dynamic Evidential Fusion, adds a concatenated pseudo-view. Both restrict mass to single classes plus the whole frame, and both are supervised. Self-supervised Trusted Contrastive Multi-view Clustering with Uncertainty Refined (STCMC-UR) brings belief fusion to clustering by using uncertainty to filter pseudo-labels. Its contrastive objective is pairwise and was tested only up to about 20k samples, and its authors state that it fails on incomplete multi-view data. We differ from all three in two ways. We allow mass on compound subsets, and we place fusion on a linear-time anchor structure rather than on per-view networks or pairwise contrast.
The complexity results both constrain the design and supply its method. Using hierarchies to efficiently combine evidence with Dempster's rule of combination proves that combination stays #P-hard even for simple support functions. The same paper shows three positive results: hierarchical evidence is combinable in polynomial time, testing whether evidence can be arranged hierarchically reduces to 2-SAT, and a fixed-parameter algorithm merges conflicting focal sets into "blobs" at cost $2^k \cdot \mathrm{poly}$ in the merge level $k$. We reuse all three pieces. The paper itself was evaluated only on a synthetic five-hypothesis eye-disease example, its authors call the merging "overly aggressive", and nobody knows what $k$ looks like on real data. Measuring that is half of this proposal.
Markov Chain Monte-Carlo Algorithms for the Calculation of Dempster-Shafer Belief supplies the approximate alternative, a random walk over non-empty intersections. It was again tested only on synthetic frames with $|\Theta|=30$, and it can stall when the valid states are poorly connected.
The anchor-graph work supplies the scaling machinery. Fast Multi-view Discrete Clustering with Anchor Graphs (FMDC) replaces $n\times n$ graphs with $n\times m$ point-to-anchor graphs and optimizes a discrete cluster assignment directly. Hierarchical Anchor Graph Learning for Multi-View Clustering (HAG-MVC) builds multi-level anchor pyramids in the original feature space in $O(n)$ and reports that four layers are usually best. Highly-efficient Incomplete Largescale Multiview Clustering with Consensus Bipartite Graph (IMVC-CBG) learns shared consensus anchors and handles missing views at 101,499 samples, where every competitor ran out of memory. All three are deterministic. None of them represents how reliable a view is for a given sample, or ambiguity between particular clusters. Note that HAG-MVC's pyramid is exactly the kind of nested structure the hierarchy result needs, although the two literatures have never met.
Research Program
We first build a consensus discrete cluster assignment over $c$ clusters in the FMDC style; these clusters form the frame $\Theta$. Each view $v$ then builds its own anchor pyramid in the HAG-MVC style. Each pyramid node is mapped to the subset of $\Theta$ covering most of the points attached beneath it, which gives a per-view tree $T_v$ of cluster subsets.
Each sample then receives a belief assignment per view, with its mass spread over the nodes of $T_v$ along and near its anchor path. Mass on a leaf means confident evidence for one cluster. Mass on an internal node means evidence that the point is somewhere in that group of clusters. Mass on the root, which is all of $\Theta$, means ignorance. Two kinds of signal set how the mass is distributed: how sharply the sample's anchor affinities concentrate, and how pure each anchor is. A missing view contributes all its mass to the root. This is how incomplete data is handled, with no imputation.
Fusion proceeds as follows. We take the union of all view trees' focal sets and run the 2-SAT test once per dataset, not once per sample, because the focal sets are shared across samples. If the union is laminar, we apply exact hierarchical combination to every sample. If it is not, we run the merging algorithm. We also test a less aggressive variant that merges only the minimal conflicting pairs found by the vertex-cover formulation. We then record the resulting $k$ and the closure size.
The fused belief is converted to a hard label with the pignistic transform, which splits each compound mass equally among its member clusters. The consensus assignment is then updated and the trees are re-labeled. These steps alternate until the assignment stops changing. Because the shared subset structure is precomputed, the per-sample cost is
$$C_{\text{sample}} = O\big(V \cdot |\mathcal{F}|\big),$$
where $V$ is the number of views and $\mathcal{F}$ is the intersection closure of the (possibly merged) view trees. For laminar unions, $|\mathcal{F}|$ is bounded by the total number of tree nodes, so the bound follows from combining one view at a time over a fixed laminar family. The total cost is linear in $n$ on top of the anchor-graph cost.
The analysis deliverable is an empirical account of $|\mathcal{F}|$, $k$, and accuracy loss from merging across real benchmarks. It answers the question the hierarchy paper left open.
Baselines
The naive reference point is FMDC run on the same anchors with no evidential layer. It uses uniform view weights and a deterministic assignment. Fast Multi-view Discrete Clustering with Anchor Graphs reports an ACC of 0.9657 on WebKB. We will match it on clean complete data. Beating it there is not required; the comparison is mainly a check that evidential fusion costs nothing when views are clean.
The strongest scalable competitor is IMVC-CBG, because it is the only method in the file that both handles missing views and finishes on YoutubeFace in 64GB. We will rerun it with the same anchor count, the same missing-view masks at ratios from 10% to 80%, and the same 64GB machine. No reported ACC on YoutubeFace was found on Lacuna for IMVC-CBG. The file gives only its sole-survivor status, plus a 19.3% accuracy gain over DAIMC on NGs. We therefore treat our own rerun as the reference. To count as a win, our method must achieve higher ACC/NMI at missing ratios of 50% and above, with wall-clock time within a small constant factor.
On complete data, HAG-MVC is the strongest deterministic hierarchy method. The file reports only relative gains for it, 15.24% ACC on Reuters and 9.60% on PIE over the second-best methods, so it will also be rerun with $L=4$ and an identical tuning grid.
The strongest evidential competitor is STCMC-UR. It reports 7.3% ACC and 15.5% NMI over the second-best method on Caltech-2V, and 100% ACC/NMI on COIL20. It is run where it fits in memory and recorded as out-of-memory or incomplete-incapable elsewhere.
The key ablation isolates compound mass. We run an identical pipeline in which each view's tree is collapsed to leaves plus root, which is TMC-style singleton-plus-ignorance fusion on the same anchors. A second ablation replaces exact hierarchical combination with the MCMC sampler at equal wall-clock time. All methods receive the same anchor initialization, the same number of tuning trials, and five seeds.
Why not just…?
Why not just keep singleton-plus-ignorance fusion, as in Trusted Multi-View Classification? This is the most serious threat. It avoids all of the complexity machinery, and it already downweights noisy views, as shown when Gaussian noise was added to half the views in Trusted Multi-View Classification. The collapsed-tree ablation tests it directly. If compound mass does not improve ACC/NMI, or the uncertainty-based detection of corrupted and missing views, then the expressiveness argument fails. In that case we would report that DST's subset reasoning does not pay off in clustering.
Why not just force one shared consensus tree across views, as IMVC-CBG shares consensus anchors? A single tree is trivially laminar, so neither 2-SAT nor merging is needed. This is a real option, and it is included as a variant. We expect view-specific trees to matter because different views confuse different cluster pairs, such as text versus image on NUS-WIDE. The experiment comparing shared and view-specific trees settles the question. If shared trees match view-specific ones, the contribution reduces to hierarchical evidential clustering, which is still new, and the FPT validation becomes a negative finding about whether it is needed.
Why not just enumerate all intersections by brute force, or approximate with MCMC? With $V$ views and four-level paths, brute force costs only $L^V$ intersections per sample, which is cheap. The hierarchy matters only when mass spreads over many nodes or when trees conflict, because then the closure can grow combinatorially. We will therefore measure brute-force time against $|\mathcal{F}|$ directly. If the closure stays small on every benchmark, brute force with caching is adequate, and we will say so. MCMC is known to stall in bottlenecked state spaces (Markov Chain Monte-Carlo Algorithms for the Calculation of Dempster-Shafer Belief), and the equal-time comparison checks whether that happens here.
Why not just average per-view probabilities over tree nodes? Averaging has no conflict normalization and no distinction between vacuous and uniform evidence, which Trusted Multi-View Classification identifies as what makes softmax fusion overconfident. We include averaging over the same tree nodes as an ablation, evaluated on the missing-view and corrupted-view curves.
Proposed Experiments
The benchmarks are WebKB, Reuters, PIE, COIL20, Caltech-2V/3V, and NUS-WIDE for accuracy, and YoutubeFace as the scaling stress test. Incomplete settings use IMVC-CBG's missing ratios from 10% to 80%. Corruption follows TMC's protocol of adding Gaussian noise to half the views. Metrics are ACC and NMI, wall-clock time and peak memory, and the AUROC of fused uncertainty for flagging corrupted or missing-view samples. We also measure how well compound mass lands on the right pairs: whether $m(\{A,B\})$ concentrates on the cluster pairs that the ground truth shows to be most confused.
Three checks decide the outcome. The first is the structural measurement, reported per dataset: whether the trees' union is laminar, the merge level $k$, and the closure size $|\mathcal{F}|$. If $|\mathcal{F}|$ grows exponentially with $c$ on real data, the efficiency claim is refuted. The second is the collapsed-tree ablation at high missingness. It is the single result that shows whether compound focal sets earn their keep. The third is a time-versus-$n$ curve on subsampled YoutubeFace up to its full 101,499 samples, within 64GB. It confirms that the evidential layer preserves linear scaling.
References
- Trusted Multi-View Classification
- Trusted Multi-View Classification With Dynamic Evidential Fusion
- Self-supervised Trusted Contrastive Multi-view Clustering with Uncertainty Refined
- Using hierarchies to efficiently combine evidence with Dempster's rule of combination
- Markov Chain Monte-Carlo Algorithms for the Calculation of Dempster-Shafer Belief
- Fast Multi-view Discrete Clustering with Anchor Graphs
- Hierarchical Anchor Graph Learning for Multi-View Clustering
- Highly-efficient Incomplete Largescale Multiview Clustering with Consensus Bipartite Graph