A lot of data analysis work has studied various aspects of graph structured data (comprising entitites, or nodes, with some pairs linked together by edges). But a simple graph is often insufficient to capture the complex relations seen in practice: although connectivity within a computer network can be represented by a graph, there are many different kinds of nodes (computers, routers, switches) and different kinds of links between them (DSL lines, fiber links etc.). Consequently, the idea of "semantic graphs"-- graphs which include this richer information on types of entities and different links between them--are of increasing interest. Moreover, in practice these graphs are not static, by changing over time as new connections are formed or discovered, leading to
dynamic semantic graphs.
Back in March,
Tina Eliassi-Rad visited DyDAn and talked about some of her recent work on
Dynamic Semantic Graph analysis. Many natural questions she introduced lead to concrete research problems:
- How to visualize a semantic graph, and adequately convey the different relationships therein?
- How to find paths of connections in semantic graphs, and determine if these are significant?
- How to efficiently find instances of a particular subgraph within a large Semantic Graph (with wildcard matching, etc.)?
- How to find patterns or anomalies within the data, indicating unexpected relations or features to investigate in more detail?
She talked in detail about the problem of learning functions within the graph. The key insights are to be able to combine ideas from both machine learning and graph theory, rather than try to reduce to one alone. The topological features of a graph are important features to provide for a learning algorithm. Fully incorporating the time-dynamics remains a major challenge.
A recent workshop at DyDAn also studied the problems of semantic graphs from a variety of perspectives -- the slides are available from the
workshop website.
