It seems that you are interested in a lossy reduction, one from which you cannot construct back the input.
In order to choose the proper lossy reduction, one should define the goal and than look for a scheme that minimise the reduction with respect to the goal.
I make some assumptions here:
- You discuss students so each student (a node) has not too many (dozens? hundreds?) relations (edges)
- You have ~ million relations so you have students from some universities.
- Therefore, most edges are local (between students from the same university or even faculty).
I would have try these directions:
Take a sample of the students. The graph obtained from the samples will represent the universities.
You can also take only students with a high number of edges those with few edges tend to have less impact of the graph structure.
You might be interested in combining the two directions above: identify local structures and then create a sub graph of students of many edges or connecting some structures.
You might also try Dbscan, a clustering algorithm based on graphs that might be handy here.