When to use graph clustering (by constructing a graph from raw data) vs conventional clustering methods? This is a conceptual question. Say I have some tabular data, and a known similarity function i want to use to compare records in this tabular data. Records correspond to members of a MileageProgram, for example, and columns have categorical features corresponding to each member (Name, Membership tier, Country of Origin, City of residence, Color of hair, etc...). I could approach this in two (and there may be more, but I'm interested in comparing these two for the moment):
Approach 1: 
One hot encode categorical variables (or find another way to embed/encode them). Use the known distance measure/function to calculate pairwise distances among the N members in my dataset. Then perform clustering using whatever makes sense for the structure of the data (e.g. K-means, DBSCAN, whatever...). Maybe throw in some dimensionality reduction
Approach 2: 
Use the known distance measure/function to calculate pairwise distances among the N members in my dataset. Apply a threshold to create linkages based on these calculated distance values, and create linkages when distances are lower than some threshold T. Employ community detection methods on graphs (correct one, TBD). 
Is there a rule of thumb to understand when to prefer Approach 1, and when to prefer Approach 2? What are the pros and cons of choosing one approach vs the other? I can see why thresholding might be a coarse step (in Approach 2) but there must be some scenarios where Approach 2 is the better approach to take? 
 A: The simple answer is “it depends on your data and the question that you are posing about your data”. Furthermore, "it may depend on who is your audience". 
I understand that you split the literature in two groups that do not "talk" very  much with each other (different periodicals, books, conferences...).
First approach: the classical and conventional approaches used in Machine Learning/Statistics.
Many possible different solutions, but as far as I know, the most popular ones are based on similarity metrics such as Euclidean distance, Cosine... 
Second approach: more common among people that belongs to the field of Networks/Complex Networks/Social Networks. Some possibilities are here.
Most solutions are based in two different concepts: (1) Modularity (2)
Surprise (you do not need actually to evaluate the distance here - are you thinking about something else?):
Let me try to defend my assertion “it depends on your data and the question that you are posing about your data” through examples:
1) Imagine that you have a network of airports in some country and the only data that you have is the flow from one airport to the other and the intention of your work is to identify “clusters” or “communities” among these possible collection of airports (for business proposals you want to know whether the average person that lives in the north of USA travels in her/his neighborhood or not) For me the most natural approach in this case would be the second approach. Note that there is no “natural similarity (distance)” to be associated with two airports in this network.  We can build (I actually did something very related to this - although the focus was not to find exactly community structure), but maybe you understand what I am trying to say: 10 people in the same room may build a different metric and some of them may not make any sense for you or for me. Anyway, it may not be natural to everyone, but we can build a similarity function and we can use the first approach.
2) Your example… Imagine now that you have a some data and a clear similarity function. I would try a method of the first approach. Because you have all you need at hand and it is more natural.
However, the things are not so simple. There are some cases that both approaches may be natural. In the end, you will need to “sell” the technique you used for someone (your boss, your advicer, yourself). It will be much easier if you use the technique your community is more used to applying in similar situations. 
If you are like me and you do not like the answer that I am giving to you, I would try to build simulate data (monte carlo simulation) that try to cover all the aspects of your data and compare the methods. However, is it possible to "model" all the aspects of the data? What is the generator process of the data? This is another difficult question.
I have not finished yet.
You compared two big fields of clustering/community detection.
Minor differences in your data or the similarity distance that you used will return different clusters. Let me give another example: 
3) As far as I know when people use the K-means usually consider the Euclidean Distance. However, if you go to the field of Natural Language Processing people prefer to use the cosine similarity because in this field they use the cos similarity among vectors of TF-IDF, that makes much more sense than the Euclidean distance in this case. Although there is a relation between the Euclidean Distance and cos similarity, you have to change the algorithm. In this case, you have to use the Spherical K-means.
A: I'm not sure whether I share your understanding of "approaches". In my understanding, DBSCAN should belong to "Approach 2", as it applies "a threshold to create linkages based on these calculated distance values, and create linkages when distances are lower than some threshold T". So I offer my answer according to my understanding and hope it helps.
If I were to "cluster" the clustering algorithms into two kinds, they would be:


*

*"Connecting algorithms", versus

*"Separating algorithms".


The names are chosen to emphasize the difference between the two, and not necessarily to describe their inner workings. Also, such a taxonomy is an oversimplification; in reality, most algorithms fall somewhere between the two extremes.
"Connecting algorithms" understand clusters as collections of observations being "similar" by some similarity measure, and thus "connecting" them into clusters. The simplest and most prototypical of these is K-means, where the similarity is expressed as "having a low distance from the cluster centroid". Agglomerating hierarchical clustering, which connects observations according to their pair-wise similarity, would be another example.
"Separating algorithms", in contrast, understand clusters as collections of observations being dissimilar (separate) from other clusters. Spectral clustering
 is probably the most prototypical for this group, as it explicitly cuts the graph along the connections with greatest separation power.
Now, when to use which type of clustering depends on your data, your similarity measure and the desired information you want to derive. As I have done some work on spectral clustering, I'm somewhat biased towards them and consider them superior in terms of achieving "good" clustering results. The drawback is that the results are hard to interpret: For each cluster, you get a list of points that belong to it, but you can't really see why it is so. On the other extreme, K-means offers a straightforward interpretation: Points in each cluster are most similar to its centroid (the "platonic ideal" of that cluster, if you want). The drawback is that it only works when your clusters are convex and symmetrical (both according to your similarity measure) around the centroids.
For your concrete problem, where you have categorical variables, I believe graph-based approaches are more appropriate than centroid-based. Computing the mean (or any kind of centroid) for categorical variables is a very unnatural thing to do, but you can naturally construct a graph by connecting the observations based on the shared values of their variables, and weighting the connections accordingly.
