# Need pointers for problem formulation

I have very little experience with graph DBs but i imagine this problem suits one

Assume a dataset with two entities , Users and Foods. A user can have a relationship with a Food, specifically they can score it from 0 to 100.

What i'd like to achieve is, for every user, find all the other users that are similar to them. By similar i mean find the Users that have also liked similar Foods and get a match so essentially im trying to build a a matchmaking system.

Algorithms such as finding friend's of friends are relatively easy to wrap my head around however im unsure as to how to approach this one and wether describing my data as a graph is even the right way to go about it.

I originally made a thought experiment to see how this would look on a relational database and its clearly quite hard to achieve as for every insert of a new Food or User, recalibration would need to happen for the entire database ( which sounds unavoidable in the first place )

I dont know what i dont know so if you could give me some pointers from here i'd be happy to follow your leads. Thanks so much.

• This is not really about graphs. You can think of a user as a vector which corresponds to the user's food preferences. You can compare two vectors by computing their inner product or angle. I suggest reading about recommender systems, in which such problems are encountered. – Yuval Filmus Jun 19 '18 at 14:41
• yeah as i kept thinking about it it doesnt sound like a graph problem. The only issue with storing vectors was , if you have 1.000.000 foods then the vector is quite large. Everytime a user enters the system they need to check against every single vector for every other user. The same applies for updates. If you have any links that can help me read more about this i'd highly appreciate it, lots of junk out there these days im afraid : / – Return-1 Jun 19 '18 at 14:59
• Usually you store these vectors in a sparse way, that is, as a list of (index,value) pairs. – Yuval Filmus Jun 19 '18 at 15:01

Yuval Filmus already pointed you towards recommender systems, which in your case is the right way to go.

However, since you asked for a graph formulation and tagged it with graph-theory, we will go out of our way to put this into such a setting.

## Definitions

A graph is called bipartite if its vertices can be partitioned into two sets, say $U$ and $V$ in such a way that all edges are between $U$ and $V$. (Coincidentally a graph is bipartite if and only if it is two-colorable.)

A bipartite graph is called complete if every edge between $U$ and $V$ are present, i.e., it is isomorphic to $K_{n,m}$ for some $n,m \in \mathbb{N}$.

A bipartite graph is called a bicluster if its connected components induce complete bipartite graphs.

## The problem

An editing problem is a graph problem where we want to add or delete (as few as possible) edges to make a graph have a certain property. So let us define Bicluster Editing as the following problem:

Given a bipartite graph $G = (V, U, E)$ and a natural number $k \in \mathbb N$, does there exists a set of edges $E'$ such that $G' = (U, V, E')$ is a bicluster and $|E \triangle E'| \leq k$ (where $\triangle$ is the symmetric difference)?

Now, what does this mean? If such a set exists for a small $k$, you have partitioned your users and foods into equivalence classes such that in every equivalence class, all the users like the same foods and all the foods are liked by the same users, changing the graph very little.

Is it practical? No. But at least it's NP-complete.