Alternative approaches to clustering and dimension reduction (UMAP in particular)

[metasoarous]

Over in #883, @JacobCWBillings mentioned:

As an alternative to thinking about a static clustering, my day job has started to work with the explicit structures that emerge in graphs. This approach works rather well for the current dataset, the Polis Opinion Matrix (POM), as elements of the matrix are topological primitives---i.e., signed edges connecting participants and comments.

Since we are only interested in how participants connect to one another, we can look at the topology of the nodal set of participants, and throw in an edge between participants if they agree about a particular comment.

Regarding clustering: clusters are then seen as the explicit occurrence of n-dimensional cliques---i.e., as sets of fully connected nodes. Minority groups are then cliques that are relatively disconnected to the majority clique complex.

Regarding embeddings: UMAP appears to be a well-motivated choice for POM sparse graphs. This because UMAP seeks to compute a topology over the dataset, and then to preserve that topology in the low dimensional space. You can actually go in and directly input POM's topological representation into UMAP. No guarantees about preserving completely disconnected groups, though, as the process of embedding imposes the bias that some distance exists between nodes. (And some completely disconnected group 'A' will still embed next to other groups 'B' and 'C' with equal probability).

Back to the idea of fairness. It's difficulty to assume distances between participants that are not present in the POM. So, perhaps it is more useful to stick to the representation of clique complexes. However, the POM is sparse because of undersampling, not because people don't have even marginal opinions about some comments. That being said, could populating the POM include some kind of vote delegation process? This might make more sense if the data generation process included something like participant vote weights? (For example, Alice might delegate 0.04% of her total votes to match Bob's votes.) The people at democracy.earth make use of weighting and delegation, though they haven't started into visualizations (https://github.com/DemocracyEarth/paper#33_Universal_Basic_Income).

This didn't strictly fall under the topic there (fair K-means), so I'm moving over here.

[metasoarous]

At the end of my day here, but a few points real quick:

UMAP does not directly apply to the polis vote matrix interpreted as a graph, since that graph in it's purest form is a (as you point out, signed) multigraph. As far as I know, UMAP only operates on unsigned/unweighted _uni_graphs (if we can call them that). So the trick is figuring out how to make this transformation. We have to be really careful here too, because doing a naive thing and just counting up the number of matching votes (even normalizing by number of comments both responded to) could very easily go awry if between participants A, B and C, A and B agreed on several comments which were more or less consensus statements (overwhelming support across participants), while A and C agreed on several comments for which there's much less consensus.

One nice thing about UMAP though that touches on something you point out is that where you don't have information about two participants (didn't vote on any of the same comments) you have the option of letting the network topology pull those two participants together or apart depending on who they might have had overlapping votes with (and those participants in turn, and so on; friend of a friend, etc).

Regarding your "clique" based clustering idea, this sounds somewhat similar to the MCL clustering method; Are you familiar with this? It doesn't directly apply to our situation, but again, could potentially be adapted.

Thanks

[JacobCWBillings]

It's never so easy, is it? Certainly, if you don't want to collapse the multigraph, you could just embed a nodal set that is the product of people and comments.

[JacobCWBillings]

What I like about topology, is that one can also just keep the multigraph concept, and iterativel lesion connected paths (e.g. one graph layer of comments). This filtration processes describes an ordered set of inclusions of a fully disconnected nodal set into some final connected object. A Topological Data Analysis (TDA) can track and compare characteristics of that multiscale system.

Towards the goal of describing conversations, I see the TDA method really well-utilized when people weight for themselves how to (iteratively) lesion multigraphs. Just like binarizing multigraphs assumes some equivalence between higher-lower levels of agreement, so too does assuming some filtration-order make assumptions about why people come together/separate.

[JacobCWBillings]

Has there been much discussion about weighted votes?

[metasoarous]

It's never so easy, is it?

Rarely :-) But I guess that's what makes it fun.

... if you don't want to collapse the multigraph, you could just embed a nodal set that is the product of people and comments.

Sure, but now you have something not particularly useful if you want to specifically see people or comments. Maybe something could be extracted from this representation, however.

...iterativel lesion connected paths

Not sure what you mean here. Can you please clarify? My assumption here is that you're talking about TDA here, and the filtration process of progressively relaxing/restricting connective thresholds.

I'm a keenly interested in topology writ large, and thus pretty naturally disposed towards the TDA approach, but confess that I don't know much about it. I'm hoping to spend some more time getting acquainted.

Has there been much discussion about weighted votes?

In a sense, though perhaps not exactly as you're thinking of it (see #217).

Thanks for your thoughts.

[JacobCWBillings]

Sure, but now you have something not particularly useful if you want to specifically see people or comments. Maybe something could be extracted from this representation, however.
I'm a keenly interested in topology writ large, and thus pretty naturally disposed towards the TDA approach, but confess that I don't know much about it. I'm hoping to spend some more time getting acquainted.

Has there been much discussion about weighted votes?
In a sense, though perhaps not exactly as you're thinking of it (see #217).

Thanks for ya'll's work on this. I think I'm still emotionally frustrated about finding work in this field. So please excuse if these emotions are bleeding over. (You'd think helping humanity self-organize would garner more support!)

Anyways, the above three points are related, so I will address them together:

Agreeing that the data exist as a multigraph. Without loss of information, one can move to a single-layer graph by taking as the nodal space the product of volunteerscomments2, where the doubling of nodes accounts for votes 'for' and for votes 'against'. Of course, one considers the set of all volunteercomment2 nodes from a single volunteer as connected with arbitrarily close proximity.

UMAP natively accepts this hyper-node single-layer graph.

Consider, now, that votes are imbued with an amount of scarcity. For example, each volunteer has exactly one vote, for which they may allot fractional votes to any of an expanding set of comments. This is a data-based method to turn your binary hyper-node graph into a weighted hyper-node graph. (Indeed, this is a different approach from #217. And more similar to democracy.earth. Admittedly, though, I need to spend more time with the codebase and its documentation to see how these ideas differ in better detail).

The weighted form has the express advantage that you can do things like a TDA-style filtration, where groups (and higher-order topological features) are represented as existing only at and beyond certain scales of agglomeration. (No more arbitrarily thresholding to induce some clustering, regardless of how the clusters are chosen.) In this way, you get, for free, an explicit statement as to how individual volunteers join into common interest groups. This data product carries with it information about what topic area(s) such groups were formed around. And, with a little extra digging, it is easy to identify classes of comments that sew division across groups.

Getting back to visualizing these data, you can utilize topological changes observed during the filtration to feed UMAP the kind of unweighted graphs it likes. And, using the 'aligned UMAP' method (https://umap-learn.readthedocs.io/en/latest/aligned_umap_basic_usage.html), 2d representations of an iteratively more fully-connected nodal set look visually appealing.

What I really like about this approach is that it wants to be interactive. You put one slider bar in each box to vote, and another slider bar in the visualization. And just like that, users can see how an extant pool of ideas draws individuals into higher-order structures.