When Grouping Algorithms Disagree
How do we best group people in a social network?
Catherine Plaisant, HCIL, University of Maryland
with Alexis Pister, Jean-Daniel Fekete, Paola Valdivia (INRIA, Saclay France)
and Paolo Buono (University of Bari, Italy)
Different algorithms produce different results when asked to group people from a social network. PK-clustering allows analysts and the system to take turns to construct and validate groups by comparing multiple algorithms. It incorporates personal knowledge in the process, and avoids being overly influenced by one randomly selected black-box algorithm.
Have you ever tried to group people for a dinner party or a conference dinner? Who should be at the same table? Who should not? There are many ways to do this, and no ground truth to evaluate how good a proposed seating is. If you hire five professionals to do the task, you will get five different groupings. This is in part because some people fit well in multiple groups, but also because each professional you hire will use different methods to group people, and professionals doing the groupings will not have all the information to do the job well. They don’t know everything you know; for example that Elise and Jacques are now dating, or that Bob and Paul had a virtual fist fight a week ago.
This is similar to what happens when we ask algorithms to split people from a social network into groups. Different grouping algorithms will group people differently. What do we when these algorithms disagree?
Grouping is important for analysts of large social networks because it allows them to describe the relationships between groups and within each group, and possibly how the groups evolve overtime. Examples of such social networks are communities of researchers writing papers with colleagues; terrorist groups whose members communicate via social media and meet in training camps; or employees of companies having business relationships, shared board members, family ties between owners, and various legal agreements connecting them.
Network data is typically described as a set of nodes, with links connecting them together. Network tools often force their users to choose which grouping algorithm to use among a list of black-box algorithms with mysterious names, such as “Louvain” or “Fluid-k2”. Users typically pick an algorithm at random, and then sometimes another one, but no-one ever tries all the algorithms and compare the results. This is exactly what our project set out to do automatically. Our prototype — called PK-Clustering — runs all the algorithms, and shows you how the results differs. For example, if all algorithms agree for a particular group it is likely to be a good grouping, but for another set of people there may be a lot of disagreement.
We have also learned a lot from observing analysts reviewing results of grouping algorithms. For example, we know that analysts often start by checking whether the suggested groups make sense. More specifically, they check if groupings that seemed obvious to them before running the analysis are indeed present in the results. For example, are Ben Shneiderman and Catherine Plaisant in the same group, as would be expected? Are my friends Peter, Paul and Mary — who are always together — grouped correctly? We describe this initial validation step as comparing results with ”prior knowledge”, i.e. what we bring to the table from past experience or prior analysis. Of course, our prior knowledge may be wrong, and we want the tool to tell us that too. If all the algorithms disagree with the prior knowledge, they might be on something important that we had missed, and that insight will advance our overall understanding.
Finally, we also know that an analyst almost invariably has information that the algorithms do not have access to — for example the fact that Elise and Jacques are now dating. This means that analysts want to be able to manually adjust the results to create the best possible groups that reflects that extra information. Similarly, when algorithms disagree about how to group a subset of people, analysts want to make the final decision about which option to pick. They may require a minimum level of consensus between algorithms for their recommendations to be taken. Those manual adjustments may be seen as biasing the results, but PK-Clustering records all the decisions made. Ultimately it remains the responsibility of the analyst to justify all decisions, not an algorithm.
One of the advantages of comparing results of several algorithms opposed to picking one randomly is that we are less likely to become fooled by the first results we see. For example after randomly picking Louvain as the algorithm to use, I am likely to believe that the proposed groups I see are just fine and never question their validity. This may be fine for setting a casual dinner party, but if the analysis is important, PK-Clustering gives you a flexible and interactive way to run all the algorithms, compare the results with their prior knowledge, adjust the results manually based on consensus, and record decisions for audit purposes.
PK-clustering is an example of user-initiated mixed-initiative visual analytics process, where the user and the system take turn to construct and validate the groups. PK-Clustering users iteratively build knowledge while avoiding being overly influenced by the results of black-box algorithms, often selected randomly.
Additional information
- Project Webpage with demos, papers, contact information, etc
The webpage is hosted at INRIA France, where the project initiated while Catherine was visiting INRIA as International Chair. - Full Paper:
Alexis Pister, Paolo Buono, Jean-Daniel Fekete, Catherine Plaisant, Paola Valdivia, Integrating Prior Knowledge in Mixed Initiative Social Network Clustering, IEEE Transactions on Visualization and Computer Graphics, 2020
DOI: ⟨10.1109/TVCG.2020.3030347⟩ - or read the preprint of the paper.
