Data
Synthetic data for demo. I asked ChatGPT to create user personas and generate data for 10 users and their retail behaviour for a month.
I used this data to create a bipartite graph as follows. The bipartite graph can be thought of a many to many function with users as domain and the retail behaviour nodes as range (just to make the visualization easier)
The personas are as follows:
Personas Descriptions
1. Alex Johnson
Age: 28, Gender: Male, Occupation: Software Developer, Income: $85,000/year, Location: San Francisco, CA
Retail Behaviors: Prefers online shopping, visits electronics stores bi-weekly, frequent coffee shops, occasional visits to clothing stores and bookstores.
2. Emma Davis
Age: 34, Gender: Female, Occupation: Marketing Manager, Income: $95,000/year, Location: New York, NY
Retail Behaviors: Frequent visitor to high-end clothing stores, beauty and cosmetic stores weekly, coffee shops daily, grocery stores bi-weekly.
3. Liam Brown
Age: 42, Gender: Male, Occupation: Construction Worker, Income: $55,000/year, Location: Houston, TX
Retail Behaviors: Regular visits to home improvement stores, grocery stores weekly, discount clothing stores monthly, and sports equipment stores bi-monthly.
4. Sophia Wilson
Age: 25, Gender: Female, Occupation: Graphic Designer, Income: $60,000/year, Location: Portland, OR
Retail Behaviors: Frequent visitor to art supply stores, coffee shops daily, clothing stores bi-weekly, and bookstores monthly.
5. Noah Martinez
Age: 30, Gender: Male, Occupation: Financial Analyst, Income: $75,000/year, Location: Chicago, IL
Retail Behaviors: Visits electronics stores monthly, grocery stores weekly, coffee shops daily, and clothing stores monthly.
6. Olivia Garcia
Age: 29, Gender: Female, Occupation: Nurse, Income: $70,000/year, Location: Miami, FL
Retail Behaviors: Frequent visits to grocery stores weekly, pharmacy weekly, beauty and cosmetics stores bi-weekly, and discount clothing stores monthly.
7. James Robinson
Age: 55, Gender: Male, Occupation: Retired, Income: $40,000/year (pension), Location: Phoenix, AZ
Retail Behaviors: Visits grocery stores weekly, pharmacy weekly, gardening stores bi-weekly, and bookstores monthly.
8. Isabella Harris
Age: 38, Gender: Female, Occupation: School Teacher, Income: $50,000/year, Location: Atlanta, GA
Retail Behaviors: Regular visits to bookstores monthly, grocery stores weekly, educational supplies stores monthly, and clothing stores bi-monthly.
9. Mason Clark
Age: 45, Gender: Male, Occupation: Restaurant Owner, Income: $100,000/year, Location: Seattle, WA
Retail Behaviors: Frequent visits to wholesale grocery stores weekly, restaurant supply stores monthly, electronics stores bi-monthly, and clothing stores quarterly.
10. Ava Lewis
Age: 22, Gender: Female, Occupation: College Student, Income: $20,000/year (part-time job), Location: Boston, MA
Retail Behaviors: Frequent visits to bookstores weekly, coffee shops daily, clothing stores bi-weekly, and grocery stores bi-weekly.
The following is the code to create a bipartite graph with users and retail behaviour:
import networkx as nx
import matplotlib.pyplot as plt
B = nx.Graph()
users = [
"Alex", "Emma", "Liam", "Sophia", "Noah", "Olivia", "James", "Isabella", "Mason", "Ava"
]
categories = [
"Electronics", "Clothing", "Coffee Shops", "Bookstores", "Grocery Stores",
"Beauty and Cosmetics", "Home Improvement", "Sports Equipment", "Gardening", "Educational Supplies"
]
B.add_nodes_from(users, bipartite=0)
B.add_nodes_from(categories, bipartite=1)
edges = [
("Alex", "Electronics", 2), ("Alex", "Clothing", 4), ("Alex", "Coffee Shops", 7), ("Alex", "Bookstores", 4),
("Emma", "Clothing", 7), ("Emma", "Coffee Shops", 7), ("Emma", "Grocery Stores", 2), ("Emma", "Beauty and Cosmetics", 7),
("Liam", "Clothing", 4), ("Liam", "Grocery Stores", 7), ("Liam", "Home Improvement", 7), ("Liam", "Sports Equipment", 2),
("Sophia", "Clothing", 4), ("Sophia", "Coffee Shops", 7), ("Sophia", "Bookstores", 4), ("Noah", "Electronics", 4),
("Noah", "Clothing", 4), ("Noah", "Coffee Shops", 7), ("Noah", "Grocery Stores", 7), ("Olivia", "Grocery Stores", 7),
("Olivia", "Beauty and Cosmetics", 4), ("Olivia", "Clothing", 4), ("James", "Grocery Stores", 7),
("James", "Gardening", 4), ("James", "Bookstores", 4), ("Isabella", "Bookstores", 4), ("Isabella", "Grocery Stores", 7),
("Isabella", "Educational Supplies", 4), ("Mason", "Electronics", 2), ("Mason", "Clothing", 1), ("Mason", "Grocery Stores", 7),
("Ava", "Bookstores", 7), ("Ava", "Coffee Shops", 7), ("Ava", "Clothing", 4), ("Ava", "Grocery Stores", 3)
]
for u, c, w in edges:
B.add_edge(u, c, weight=w)
To see how it looks like we’ll visualize the relations:
pos = {node: (0, i) for i, node in enumerate(users)}
pos.update({node: (1, i) for i, node in enumerate(categories)})
edge_labels = nx.get_edge_attributes(B, 'weight')
nx.draw(B, pos, with_labels=True, node_color=['lightblue']*len(users) + ['lightgreen']*len(categories), node_size=300)
nx.draw_networkx_edge_labels(B, pos, edge_labels=edge_labels)
plt.show()
We’ve created a bipartite graph using networkx library, we can access users by :
top_nodes = {n for n, d in B.nodes(data=True) if d['bipartite'] == 0}Where we call B.nodes to access all the nodes of the graph and we get the node attributes in d where we filter the nodes of type 0 of bipartite graph, for behaviour we can do the same and use 1 instead of 0
Similiarly for edges and edge attributes, we call networkx function on to the bipartite graph, nx.get_edge_attributes(B, ‘weight’) which is the number of times they visited the store in a month.
Projections
Now we need to project the graph into an embedding space, to apply our fancy algorithms and NN on top of this.
My specific intention here was to create a user embedding space where each user was linked to the other based on its behaviour.
In simple terms you can imagine your user to be a 1d vector or a tensor of length 10 (representing 10 retail behaviours) with each corrosponding term belonging to the value of that behaviour, in this case e.g. we could assume the weight or value of the behaviour is the number of visits in a month.
Now in this embedding space, if the overall behaviour is similiar, users would be closer, we use the same idea on a graph – we want to project users into an embedding space using graph techniques on the knowledge graph we have.
To create embeddings there are several well known options available, i investigated a few to fit into our use case of creating embeddings for a bipartite graph.
*In my actual data I’ve normalized the value – which here is frequency of visits, but I’m leaving it as is here in our example for ease of explanation
NetworkX Projections
There’re two inbuilt projection function provided by networkX, lets discuss what they’re, how they work and what do they look like. We’ve methods like:
Projected Graph
Lets start with projected_graph
from networkx.algorithms import bipartite G = bipartite.projected_graph(B,nodes_set_0)
Displaying the graph
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='skyblue', node_size=15, font_size=12)
plt.title("Projected Graph")
plt.show()
For the above graph we see if we do list(G.edges) that there are no edge weights, so all connections between users are equivalent
Here you also see a single connection represents 1 or more shared behaviour nodes between the users. One could also use the multigraph attribute to have an edge for each node shared.
For our specific use case this doesn’t work, because all connections are equivalent, as long as the user shares a node its linked, e.g. Ava (College student frequenting book stores & coffee shops) is linked to Sophia (Young graphic designer also frequenting bookstores and coffe shops) as she is linked to Mason (Restaurant owner frequenting DIY stores and restaurant supplies)
Weighted projected Graph
Weighted Projected graph adds weights to the connections based on the number of nodes shared
If you use nx.get_edge_attributes(G, ‘weight’), you’d be able to see the weight associated with each node.
Hence, we see here Ava is linked to Sophia by 3 as they share 3 retail stores and she is linked to Mason by 2 because they share 2.
Now the problem with this one is, it doesnt take into account frequency of visits, popularity of nodes, e.g. it connects Ava to every other node in the list, whereas for Ava’s behaviour we know:
{'Bookstores': {'weight': 7}, 'Coffee Shops': {'weight': 7}, 'Clothing': {'weight': 4}, 'Grocery Stores': {'weight': 3}}
Bottom nodes connected to Ava sorted by node degrees and edge weights:
Clothing with 8 connections and edge weight 4
Grocery Stores with 8 connections and edge weight 3
Bookstores with 5 connections and edge weight 7
Coffee Shops with 5 connections and edge weight 7
Grocery stores and clothing stores are very popular nodes with almost everyone visiting them, so, we should find a way to give lower preference to very high degree behaviours and for mason the electronics store are probably more distinctive factor because they are lowest degree and second highest frequency. (there are other caveats here as well for our use case, like for coffee store and bookstore are equal node degrees but coffee stores in general have higher edge weight so bookstores must be given more preference since they can act as a distinguishing facror, but all that comes later)
Collaboration weighted projected graph
This method works with Newman’s weighted projections often used in organic chemistry to represent molecular structures. In our case the formula would look something like this:
Good for us it is already built into the networkX library, calling onto the collaboration_weighted_projected_graph, our projected graph looks somewhat like:
Lets analyze the case of Ava, she shares:
Clothing (weight=4) - Alex, Emma, Liam, Noah, Sophia, Olivia, Mason (degree=8)
Coffee Shops (weight=7) -Alex, Emma, Noah, Sophia (degree=5)
Bookstores (weight=7) - Alex, Sophia, James, Isabella (degree=5)
Grocery Stores (weight=3) - Emma, Liam, Noah, Olivia, Isabella, James (degree=8)
New Nodes connected to Ava sorted by edge weights:
Alex with 9 connections and edge weight 0.6428571428571428
Sophia with 9 connections and edge weight 0.6428571428571428
Emma with 9 connections and edge weight 0.5357142857142857
Noah with 9 connections and edge weight 0.5357142857142857
James with 9 connections and edge weight 0.39285714285714285
Isabella with 9 connections and edge weight 0.39285714285714285
Liam with 9 connections and edge weight 0.2857142857142857
Olivia with 9 connections and edge weight 0.2857142857142857
Mason with 9 connections and edge weight 0.2857142857142857
Based on the above information, you can see that Ava has 4 behaviors, but two of them clothing and groceries are so common that they can hardly be considered as distinguishing factors. Therefore the weight for similiarity is dominated by coffee shops and bookstores and both of them are shared by Alex and Sophia, hence both of them have equal weight (same number of neighbors)
Now this still doesnt completely fit our usecase, because its not taking into account the edge weight, Ava is equally related to Alex as she’s to Sophia when Sophia exhibits more frequency for bookstores but that information isn’t being used.
Overlap weighted projected graph
This method employs Jaccard Index for projection
Where the numerator represents the common neighbors of user u and v and the denominator represents all the unique neighbors for both the users.
0 means they share nothing in common, 1 means they have exactly all in common.
Applying this to our graph, we get,
Once again if we look at Ava’s new neighbors:
Common neighbors of Ava with other top nodes and their degrees:
Sophia has 3 common neighbors: ['Bookstores', 'Clothing', 'Coffee Shops'], degree: 3
Liam has 2 common neighbors: ['Clothing', 'Grocery Stores'], degree: 4
Emma has 3 common neighbors: ['Clothing', 'Coffee Shops', 'Grocery Stores'], degree: 4
James has 2 common neighbors: ['Bookstores', 'Grocery Stores'], degree: 3
Isabella has 2 common neighbors: ['Bookstores', 'Grocery Stores'], degree: 3
Olivia has 2 common neighbors: ['Clothing', 'Grocery Stores'], degree: 3
Noah has 3 common neighbors: ['Coffee Shops', 'Clothing', 'Grocery Stores'], degree: 4
Alex has 3 common neighbors: ['Bookstores', 'Coffee Shops', 'Clothing'], degree: 4
Mason has 2 common neighbors: ['Clothing', 'Grocery Stores'], degree: 4
As we see, Ava has highest common neighbors with Sophia, Emma, Noah and Alex, out of which Sophia has the least degree, leading to a higher Jaccard’s index followed by Emma, Noah and Alex
Bottom nodes connected to Ava :
Sophia with 9 connections and edge weight 0.75
Alex with 9 connections and edge weight 0.6
Emma with 9 connections and edge weight 0.6
Noah with 9 connections and edge weight 0.6
Olivia with 9 connections and edge weight 0.4
James with 9 connections and edge weight 0.4
Isabella with 9 connections and edge weight 0.4
Liam with 9 connections and edge weight 0.3333333333333333
Mason with 9 connections and edge weight 0.3333333333333333
This information helps us look at the graph in a different way,this is similiar to the newman’s method but instead of correcting for the popularity of behaviour we correct for the popularity of node.
In our case we most likely are bound to use a mix of these, but ofcourse taking into account the edge attributes we’ve been mentioning all along.
Generic weighted projected graph
This is literally last but not the least, which allows user defined functions to be used for projections which is what we wanted.
Let’s use the example mentioned in the networkx documentation, because i’m lazy right now, applying the following code, we get:
def my_weight(G, u, v, weight="weight"):
w = 0
for nbr in set(G[u]) & set(G[v])
w += G[u][nbr].get(weight, 1) + G[v][nbr].get(weight, 1)
return w
G = bipartite.generic_weighted_projected_graph(B, nodes_set_0, weight_function=my_weight)
Here we are just summing up the weights for all the edges.
I created a custom function which is what we ended up using that takes into account the neighbors and the edge weights and creates a projection
def custom_similiarity(G, u, v, weight="weight"):
current_node = u #user 1
given_neighbor = v #user 2
# for nbr in set(G[given_neighbor]):
common_behaviors = set(G.neighbors(current_node)).intersection(G.neighbors(given_neighbor))
common_neighbor_count = len(common_behaviors)
deg_u = len(set(G.neighbors(current_node)))
deg_v = len(set(G.neighbors(given_neighbor)))
sum_edge_weight = 0
for behavior in common_behaviors:
deg_behaviour = len(set(G.neighbors(behavior)))
sum_edge_weight += G[current_node][behavior]['weight'] / deg_behaviour
print(f"{current_node},{given_neighbor} common_neighbors: {common_neighbor_count}, edge_weight:{sum_edge_weight}, behavior:{common_behaviors}")
w = (common_neighbor_count + 1) * (sum_edge_weight +1) / (deg_u*deg_v) # +1 to avoid zero probability
return round(w,3)
Check out the file on colab / github – https://github.com/w-winnie/MLSandbox/blob/main/UserBehaviourGraph_projection_livnlearnversion.ipynb
Keep an eye for more articles coming up in the next few days explaining Random Walk, node 2 vec etc
