David Suter (Edith Cowan University): Independence Complexes of Hypergraphs, Influence of Boolean Functions, and MaxCon Robust Fitting.

Maximum Consensus Fitting is a popular approach to robust fitting, particularly in computer vision. It
is formally equivalent to Maximum Independent (Stable) Set problem of a hypergraph (of minimum
sized infeasible data points). Unlike a general independent set problem, MaxCon comes with an
oracle of independence (l-infinity fit).
The main impetus of this talk, is that hypergraph classes ought to serve as a taxonomy of the
difficulty of data for MaxCon fitting. As a first step towards exploring this notion, we investigate a
hypergraph generalisation of Threshold Graphs. First, the ideal single structure characterization of
Tennakoon et. al. (CVPR2021) and Zhang et al. (CVPR2022) is shown to be a special case of this
hypergraph class (Complete Split Hypergraph Class). However, the main result is that that the
inlier/outlier (corresponding to membership or otherwise of the maximum independent set)
characterization by the size of the Influence (from Boolean Monotone Function theory) is shown to
extend from the Complete Split Hypergraph Class (a.k.a. ideal single structure of Tennakoon and
Zhang et. al.) to the whole Hypergraph class generalizing the Threshold graph class. Moreover, we
characterise the how the separation changes with the addition of vertices in this hypergraph class –
a result that justifies the notion that one should approach classification of inlier/outlier (membership
of the maximum independent set or not) by an iterative approach of eliminating one vertex at a time
and re-estimating the Influence: rather than a single shot round of estimation followed by
classification. This provides theoretical backing for the essence of the iterative schemes empirically
developed in Tennakoon and Zhang et. al. In some sense this illustrates that the Complete Split

Hypergraph class and the more general “Threshold Hypergraph Class”, grade the data into degree of
“ideal”.
To conclude the presentation, we speculate that a more complete picture of the landscape of data
complexity for MaxCon solution – and perhaps how this might relate to a more general theory of
complexity in Hypergraph theory. It is hoped that the talk might be of interest to those with a
background in computer vision and perhaps in hypergraph theory or computational complexity
theory.
This is joint work with several people: primarily Erchuan Zhang; but also Ruwan Tennakoon, Tat-Jun
Chin, Ali Bab-Hadiashar.

Biography
David Suter is currently a research professor at Edith Cowan University (Perth, Western Australia).
Previously he was a Professor at the University of Adelaide (South Australia) and at Monash
University (Melbourne, Australia). His research interests cover many aspects of computer vision and
image analysis, machine learning, and artificial intelligence. A major focus has been on robust fitting.
He holds a BSc. in applied math and physics (The Flinders University of South Australia), and a PhD in
Computer Vision (La Trobe University, Melbourne, Australia). He has served on the Australian
Research Council, College of Experts, and on the editorial board of several journals (e.g.,
International Journal of Computer Vision, Pattern Recognition).