An attributed graph was defined to represent both structural and semantic information contained in structural objects. When uncertainty exists in description of a structural object either due to noise or minor deformation, a probabilistic description of the object ensemble is necessary. For this purpose, we define an attributed random graph, which can be considered as a generalization of conventional ones, to include multiple attributes as well as numeric attribute instead of a single nominal attribute in random vertices and edges. Then, we derived the equations for an entropy of a random graph to reflect the variability of the random graph.
For the representation of a complex object, the object is decomposed into several parts, and it is described by these decomposed parts and their relations. In general, the parts can be the primitive elements that can not be decomposed further, or still can be decomposed into their subparts. Therefore, the hierarchical description method is very natural and the hierarchical description is represented by a hierarchical graph whose vertices represent either primitive elements or graphs. This graphs also have vertices which contain primitive elements or graphs. When some uncertainty exists in the hierarchical description of a complex object either due to noise of minor deformation, a probabilistic description of the object ensemble is also necessary. For this purpose, we formally define the hierarchical attributed random graph and derive the equations for the entropy calculation of the hierarchical random graph.
We adopt this concepts to three parts to computer vision and machine learning such as incremental clustering of attributed graphs, optimal isomorphism between two random graphs and optimal isomorphism between two hierarchical attributed graphs. First, we introduce an incremental clustering system to group the patterns represented by attributed graphs as an application example. The purpose of this system is to take a succession of attributed graphs and build up a concept hierarchy that summarizes and organizes input instances. For this purpose, we define a new criterion function based on entropy minimization for the incremental clustering of attributed graphs. For the attributed graph as an input instance, the clustering algorithm incrementally obtains a concept hierarchy in a top-down manner using the hill climbing strategy. It is shown that the execution of the incremental clustering algorithm and classification algorithm can be interleaved since the concept hierarchy is constructed incrementally.
Then, we adopt an entropy concept in random graph finding the optimal isomorphism between two random graphs as application example. The problem is formulated as a state-space search problem. The branch-and-bound algorithm using an efficient evaluation function is used to speed up the search. For this algorithm, we derive a consistent lower bounded estimate for an evaluation function from the entropy characteristics.
Finally, we formulated the hierarchical graph isomorphism problem as a state-space tree search problem, and the branch-and-bound algorithm is proposed to solve this problem. In the hierarchical graph isomorphism problem, if this problem is formulated as a state-space tree problem, it can also be solved by a branch-and-bound algorithm. This algorithm is a generalization of graph optimal isomorphism because hierarchical graph is a generalization of graph. From above three application examples, the usage of the random graph and hierarchical random graph can be known, we will introduce many application examples to the Chapter 7 for the applicability of these concepts.
임의의 사건(event)이나 물체(object)를 구조적으로 서술하기 위하여 속성 그래프(attributed graph)가 사용될 수 있으며, 만약 이 구조적 물체 나 사건의 모델을 구성하는데 외부 잡음이나 약간의 변형에 의하여 모호성이 존재하면 이것을 확률적으로 서술하는 것이 필요하게 된다. 이를 위하여 본 논문에서 속성 랜덤 그래프(attributed random graph)가 정의 되었으며, 또한 이 랜덤 그래프의 변화성(variability)을 살펴보기 위하여 속성 랜덤 그래프의 엔트로피를 정의하고, 이를 쉽게 계산할 수 있는 식들을 유도하였다.
복잡한 사건이나 물체의 표현을 위하여, 계층적 서술 방법(hierarchical description method)은 매우 자연스러우며, 이 계층적 서술 방법은 계층적 속성 그래프 (hierarchical attributed graph)에 의해서 표현될 수 있다. 만일 계층적 서술에 모호성이 첨가되면, 확률적 표현이 필요하며 이를 위하여 계층적 속성 랜덤 그래프(hierarchical attributed random graph)를 정의하고 엔트로피를 구하는 식들을 유도하였다.
속성 랜덤 그래프와 계층적 속성 랜덤 그래프는 과학 및 공학의 여러 분야에 이용할 수 있으며, 이 개념들의 유용성을 살펴보기 위하여 컴퓨터 비젼(computer vision) 및 기계학습(machine learning)에 관련된 세 분야에 적용하여 보았다.
먼저, 첫번째 응용예로서 속성그래프로 표현되는 패턴(pattern)들을 점진적으로 집단화 하는 문제(incremental clustering problem)에 적용시켜 보았다. 이 문제는 속성 그래프들이 연속적으로 입력되어 질때, 이전의 속성 그래프들로 만들어진 HOKB(Hierarchical Object Knowledge Base)에 새로이 입력된 속성 그래프를 포함하는 HOKB를 개념적으로 구성하는 것이며, 이를 위하여 엔트로피에 근거한 새로운 평가함수를 정의하고 이를 이용한 알고리즘을 소개하였다.
두번째 응용예로서, 두개의 랜덤 그래프 사이의 정합 (matching)을 위하여 엔트로피의 개념을 이용하였다. 즉 이 문제를 상태 공간 나무 탐색 문제 (state space tree search problem)로 정형화 한뒤, 이 문제를 해결하기 위하여 엔트로피에 근거한 평가함수를 유도하고 이를 이용한 Branch-and-Bound 알고리즘을 제시하였다.
세번째 응용예로서, 두개의 계층적 속성 그래프 사이의 정합 문제를 해결하기 위하여 이를 계층적 상태 공간 나무 탐색 문제(hierarchical state space tree search problem)로 정형화시키고, 이 문제를 해결하기 위하여, 확장된 Branch-and-Bound알고리즘을 제안하였다.
이 세 가지 응용 예를 통하여 속성 랜덤 그래프와 계층적 속성 랜덤 그래프의 유용성을 알 수 있었으며, 더 많은 응용 예들을 추후과제 에서 소개하였다.
