Monotone Violation Graph

This is part of an algorithm developed by Wouter Duivesteijn as part of a Masters Thesis.  Description of the algorithm can be found here.  Duivesteijn look at the problem in terms of monotonicity constraints in the context of nearest neighbour classification.  In the past, we’ve looked at nearest neighbour algorithms for data approximation, so we’ll probably look at the data towards that.

After the monotone violation graph is created, Duivesteijn and Feelders employ a max flow optimisation approach in order to relabel the monotone data.

The R-code needs a couple of things that might be automatically available in matlab, i.e. you need to define the partial order for multivariate data, you also need to make use of the setdiff function in order to filter out the data.  With these, the code is reasonably easy to implement.

I know the pseudo-algorithm given by the original authors is better from a comprehension point of view, but i’ll just summarise for the sake of the R code:


1. read the training data as x1 … xn   y-label

2. normalise the xi (columns of the data – not the labels)

3. define a function which specifies the partial order over X^n

4. mark 1s in the MVG matrix based on the partial order

5. create a vector containing each of the non-violating points and filter these entries from the matrix

6.  from the filtered matrix, create an edges array that can be used in the optomisation algorithm


required input:  training data

# first read data
D <- read.table("documents/R/train1.txt")
# normalise columns
normD <- D
for(i in 1:nrow(D)) for(j in 1:(ncol(D)-1)) 
#define the partial order
if(sum(as.numeric(x[1:n]<=y[1:n]))==n) {1} else {0}
# prepare mvg matrix
mvgAdjMatrix <-matrix(0,nrow(D),nrow(D))
#fill mvgAdjMatrix
for(i in 1:nrow(D)) for(j in 1:nrow(D)) {
# make the nonviolating points vector
for(i in 1:nrow(D)) {
if(   sum(mvgAdjMatrix[i,])+sum(mvgAdjMatrix[,i]) ==0) {
# remove the nonviolatingpoints from mvg matrix
mvgAdjMatrix <- mvgAdjMatrix[setdiff(tBR,nonViolatingPoints),setdiff(tBR,nonViolatingPoints)]
# create the edges array that is used by the opt alg
for(i in 1:nrow(mvgAdjMatrix)) for (j in 1:nrow(mvgAdjMatrix)) { 
if(mvgAdjMatrix[i,j]==1) {
a2[1]<-i ; a2[2]<-j ; mvgEdges<-rbind(mvgEdges,a2)}

One response to “Monotone Violation Graph

  1. Pingback: Monotonicity Check | Aggregation Functions

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s