그래프 이론으로는 충분하지 않습니다.

정점(점)과 모서리(이를 연결하는 선)와 같은 일반적으로 네트워크에 의존하는 연결에 대해 이야기하기 위한 수학적 언어는 적어도 18세기 이후로 실제 현상을 모델링하는 귀중한 방법이었습니다. 그러나 수십 년 전 거대한 데이터 세트의 출현으로 연구자들은 도구 상자를 확장해야 했으며 동시에 새로운 수학적 통찰력을 적용할 수 있는 거대한 샌드박스를 제공했습니다. 그 이후로 말했다. 조시 그로초우, 콜로라도 대학 볼더의 컴퓨터 과학자에 따르면, 연구자들이 빅 데이터의 노이즈 속에서 복잡한 구조와 신호를 찾을 수 있는 새로운 종류의 네트워크 모델을 개발함에 따라 급격한 성장의 흥미진진한 시기가 있었습니다.

Grochow는 빅 데이터에서 연결을 찾는 것과 관련하여 그래프 이론에는 한계가 있다고 지적하는 점점 더 많은 연구원 중 하나입니다. 그래프는 모든 관계를 쌍 또는 쌍을 이루는 상호 작용으로 나타냅니다. 그러나 많은 복잡한 시스템은 이진 연결만으로는 표현할 수 없습니다. 이 분야의 최근 진행 상황은 앞으로 나아가는 방법을 보여줍니다.

육아의 네트워크 모델을 구축하는 것을 고려하십시오. 분명히 각 부모는 자녀와 연결되어 있지만 그래프 이론이 모델링할 수 있는 것처럼 육아 관계는 단순히 두 연결의 합이 아닙니다. 동료 압력과 같은 현상을 모델링하려는 경우에도 마찬가지입니다.

“직관적인 모델이 많이 있습니다. 소셜 역학에 대한 동료 압력 효과는 데이터에 이미 그룹이 있는 경우에만 캡처됩니다.”라고 말했습니다. 레오니 노이하우저 독일 RWTH Aachen 대학의 그러나 이진 네트워크는 그룹 영향을 포착하지 않습니다.

수학자 및 컴퓨터 과학자는 이진 링크가 아니라 그룹 역학이 개별 행동에 영향을 미칠 수 있는 이러한 복잡한 방식을 설명하기 위해 "고차 상호 작용"이라는 용어를 사용합니다. 이러한 수학적 현상은 양자 역학의 얽힘 상호 작용에서 인구를 통해 확산되는 질병의 궤적에 이르기까지 모든 영역에서 나타납니다. 약리학자가 모델링을 하고 싶다면 약물 상호 작용예를 들어, 그래프 이론은 두 가지 약물이 서로 어떻게 반응하는지 보여줄 수 있지만 세 가지 경우는 어떻습니까? 아니면 XNUMX개?

이러한 상호 작용을 탐색하는 도구가 새로운 것은 아니지만 고차원 데이터 세트가 수학자 및 네트워크 이론가에게 새로운 아이디어를 제공하는 발견을 위한 엔진이 된 것은 최근 몇 년입니다. 이러한 노력은 그래프의 한계와 확장 가능성에 대한 흥미로운 결과를 낳았습니다.

"이제 우리는 네트워크가 사물의 그림자일 뿐이라는 것을 알고 있습니다."라고 Grochow가 말했습니다. 데이터 세트에 복잡한 기본 구조가 있는 경우 이를 그래프로 모델링하면 전체 스토리에 대한 제한된 예측만 표시될 수 있습니다.

"수학적 관점에서 우리가 사물을 연구하는 데 사용한 데이터 구조가 데이터에서 보고 있는 것과 완전히 맞지 않는다는 것을 깨달았습니다."라고 수학자가 말했습니다. 에밀리 퍼빈 태평양 북서부 국립 연구소의

이것이 수학자, 컴퓨터 과학자 및 기타 연구자들이 고차 현상을 탐구하기 위해 여러 가지 형태로 그래프 이론을 일반화하는 방법에 점점 더 집중하는 이유입니다. 지난 몇 년 동안 이러한 상호 작용을 특성화하고 고차원 데이터 세트에서 수학적으로 검증하기 위해 제안된 방법이 급류했습니다.

Purvine에게 고차 상호작용에 대한 수학적 탐구는 새로운 차원의 매핑과 같습니다. "XNUMX차원 토지 플롯의 기초로 그래프를 생각해 보세요."라고 그녀는 말했습니다. 위로 올라갈 수 있는 XNUMX차원 건물은 크게 다를 수 있습니다. “지상으로 내려가면 똑같아 보이지만 위에서 짓는 것은 다릅니다.”

하이퍼그래프 입력

이러한 고차원 구조에 대한 검색은 수학이 특히 모호하고 흥미로워지는 곳입니다. 예를 들어 그래프의 고차 유사체를 하이퍼그래프라고 하며 모서리 대신 "하이퍼에지"가 있습니다. 이들은 여러 노드를 연결할 수 있습니다. 즉, 다중 방향(또는 다중 선형) 관계를 나타낼 수 있습니다. 선 대신에 하이퍼 에지는 세 개 이상의 장소에 말뚝을 박은 방수포와 같은 표면으로 볼 수 있습니다.

괜찮습니다. 하지만 이러한 구조가 기존 구조와 어떤 관련이 있는지에 대해 아직 모르는 부분이 많이 있습니다. 수학자들은 현재 그래프 이론의 어떤 규칙이 고차 상호작용에도 적용되는지 배우고 있으며, 새로운 탐구 영역을 제안합니다.

하이퍼그래프가 빅 데이터 세트에서 추출할 수 있는 관계의 종류를 설명하기 위해 퍼바인은 과학 출판의 세계인 집에 가까운 간단한 예를 가리킵니다. 각각 최대 XNUMX명의 수학자가 공동 저술한 논문을 포함하는 두 개의 데이터 세트를 상상해 보십시오. 간단히 하기 위해 A, B 및 C로 이름을 지정하겠습니다. 하나의 데이터 세트에는 XNUMX개의 논문이 포함되어 있으며 XNUMX개의 고유한 쌍(AB, AC 및 BC) 각각에 의한 XNUMX개의 논문이 있습니다. 다른 하나는 세 명의 수학자(ABC)가 공동 저술한 총 XNUMX개의 논문만 포함합니다.

두 데이터 세트에서 가져온 공동 저자의 그래프 표현은 삼각형처럼 보일 수 있으며, 이는 각 수학자(XNUMX개의 노드)가 다른 두 개(XNUMX개의 링크)와 협력했음을 보여줍니다. 누가 누구와 협력했는지가 유일한 질문이라면 하이퍼그래프가 필요하지 않을 것이라고 Purvine은 말했습니다.

그러나 하이퍼그래프가 있다면 덜 명확한 구조에 대한 질문에 답할 수도 있습니다. 예를 들어, 첫 번째 세트(XNUMX개 논문 포함)의 하이퍼그래프에는 각 수학자가 XNUMX개의 논문에 기여했음을 보여주는 하이퍼에지가 포함될 수 있습니다. 두 세트의 하이퍼그래프를 비교하면 논문의 저자가 첫 번째 세트에서는 다르지만 두 번째 세트에서는 동일하다는 것을 알 수 있습니다.

야생의 하이퍼그래프

이러한 고차원적 방법은 생태학자들이 1990년대에 옐로스톤 국립공원에 늑대를 재도입하여 생물다양성과 먹이 사슬 구조의 변화를 촉발한 방법을 보여주었을 때와 같이 응용 연구에서 이미 유용한 것으로 입증되었습니다. 그리고 최근 한 종이, Purvine과 그녀의 동료들은 관련된 가장 중요한 유전자를 식별하기 위해 하이퍼그래프를 사용하여 바이러스 감염에 대한 생물학적 반응 데이터베이스를 분석했습니다. 그들은 또한 그래프 이론이 제공하는 일반적인 쌍별 분석에서 이러한 상호 작용이 어떻게 놓쳤는지 보여주었습니다.

Purvine은 "이것이 하이퍼그래프에서 그래프를 뛰어넘는 힘을 보고 있는 것입니다."라고 말했습니다.

그러나 그래프에서 하이퍼그래프로 일반화하는 것은 빠르게 복잡해집니다. 이것을 설명하는 한 가지 방법은 다음과 같은 질문을 하는 그래프 이론의 표준 절단 문제를 고려하는 것입니다. 그래프에 두 개의 개별 노드가 주어졌을 때 둘 사이의 모든 연결을 완전히 끊기 위해 절단할 수 있는 최소 모서리 수는 얼마입니까? 많은 알고리즘은 주어진 그래프에 대한 최적의 컷 수를 쉽게 찾을 수 있습니다.

그러나 하이퍼그래프를 자르는 것은 어떻습니까? "커트라는 개념을 하이퍼그래프로 일반화하는 방법에는 여러 가지가 있습니다."라고 말했습니다. 오스틴 벤슨, 코넬 대학의 수학자. 그러나 그는 하이퍼에지가 다양한 방법으로 절단되어 새로운 노드 그룹을 생성할 수 있기 때문에 명확한 해결책은 없다고 말했습니다.

두 명의 동료 Benson과 함께 최근에 시도한 하이퍼그래프를 분할하는 모든 다양한 방법을 공식화합니다. 그들이 발견한 것은 다양한 계산 복잡성을 암시합니다. 일부 상황의 경우 문제는 다항식 시간에 쉽게 해결되었습니다. 이는 기본적으로 컴퓨터가 합리적인 시간에 솔루션을 빠르게 처리할 수 있음을 의미합니다. 그러나 다른 사람들에게는 문제가 기본적으로 해결할 수 없었습니다. 해결책이 존재하는지 여부를 확실히 아는 것은 불가능했습니다.

Benson은 "아직 미해결 질문이 많이 있습니다. “이러한 불가능한 결과 중 일부는 그래프로 축소할 수 없기 때문에 흥미롭습니다. 그리고 이론적인 측면에서, 그래프에서 찾을 수 있는 것으로 축소하지 않았다면 거기에 새로운 것이 있다는 것을 보여주는 것입니다.”

수학 샌드위치

 그러나 하이퍼그래프가 고차 상호작용을 탐색하는 유일한 방법은 아닙니다. 토폴로지(개체를 늘리거나 압축하거나 변형할 때 변경되지 않는 기하학적 속성에 대한 수학적 연구)는 보다 시각적인 접근 방식을 제공합니다. 위상 학자는 네트워크를 연구할 때 모양, 표면 및 치수를 찾습니다. 그들은 두 노드를 연결하는 에지가 XNUMX차원이라는 점에 주목하고 서로 다른 네트워크에 있는 XNUMX차원 객체의 속성에 대해 질문할 수 있습니다. 또는 세 개의 노드를 연결하여 형성된 XNUMX차원 삼각형 표면을 보고 비슷한 질문을 할 수도 있습니다.

위상 학자들은 이러한 구조를 단순 복합체. 이것은 사실상 토폴로지의 프레임워크를 통해 볼 수 있는 하이퍼그래프입니다. 기계 학습의 일반적인 범주에 속하는 신경망은 좋은 예를 제공합니다. 그것들은 우리 뇌의 뉴런이 정보를 처리하는 방식을 모방하도록 설계된 알고리즘에 의해 구동됩니다. 사물 간의 연결을 쌍별 연결로 모델링하는 그래프 신경망(GNN)은 대규모 데이터 세트에서 누락된 데이터를 추론하는 데 탁월하지만 다른 애플리케이션에서와 마찬가지로 XNUMX개 이상의 그룹에서만 발생하는 상호 작용을 놓칠 수 있습니다. 최근 몇 년 동안 컴퓨터 과학자들은 단순 신경망, 이러한 효과를 찾기 위해 GNN의 접근 방식을 일반화하기 위해 고차 복합물을 사용합니다.

단순 콤플렉스는 토폴로지를 그래프 이론에 연결하고 하이퍼그래프와 마찬가지로 향후 조사를 주도할 설득력 있는 수학적 질문을 제기합니다. 예를 들어, 토폴로지에서 단순 콤플렉스의 특수한 종류의 하위 집합도 그 자체가 단순 콤플렉스이므로 동일한 속성을 갖습니다. 하이퍼그래프에 대해 동일하게 적용되는 경우 하위 집합에는 포함된 모든 양방향 모서리를 포함하여 내부의 모든 하이퍼에지가 포함됩니다.

하지만 항상 그런 것은 아닙니다. Purvine은 "현재 우리가 보고 있는 것은 데이터가 모든 하이퍼에지나 모든 복잡한 상호 작용이 다른 모든 것과 동일한 크기가 아닌 중간 지점에 속한다는 것입니다."라고 말했습니다. "세 방향 상호작용은 가능하지만 쌍방향 상호작용은 불가능합니다." 빅 데이터 세트는 생물학적 신호 네트워크 또는 동료 압력과 같은 사회적 행동에서 그룹의 영향이 종종 개인의 영향을 훨씬 능가한다는 것을 분명히 보여주었습니다.

Purvine은 데이터를 일종의 수학적 샌드위치의 중간을 채우는 것으로 설명합니다. 위쪽은 토폴로지의 아이디어로, 아래쪽은 그래프의 한계로 묶입니다. 네트워크 이론가들은 이제 고차 상호작용을 위한 새로운 규칙을 찾아야 합니다. 그리고 수학자들에게 그녀는 "놀아볼 여지가 있다"고 말했다.

랜덤 워크 및 매트릭스

이러한 창의적인 "놀이" 감각은 다른 도구에도 적용됩니다. Benson은 그래프와 데이터를 설명하는 다른 도구 사이에는 온갖 종류의 아름다운 연결이 있다고 말했습니다. "하지만 상위 설정으로 이동하자마자 이러한 연결이 더 어려워집니다."

그는 마르코프 체인의 고차원 버전을 고려하려고 할 때 특히 분명하다고 말했습니다. Markov 체인은 다음 단계가 요소의 현재 위치에만 의존하는 다단계 프로세스를 설명합니다. 연구자들은 Markov 모델을 사용하여 정보, 에너지, 심지어 돈과 같은 것들이 시스템을 통해 흐르는 방식을 설명했습니다. 아마도 Markov 체인의 가장 잘 알려진 예는 각 단계가 이전 단계에서 무작위로 결정되는 경로를 설명하는 랜덤 워크입니다. 랜덤 워크는 특정 그래프이기도 합니다. 그래프를 따라 걷는 모든 워크는 링크를 따라 노드에서 노드로 이동하는 시퀀스로 표시될 수 있습니다.

그러나 걷기처럼 간단한 것을 확장하는 방법은 무엇입니까? 연구원들은 현재 위치에만 의존하는 대신 많은 이전 상태를 고려할 수 있는 고차 Markov 체인으로 전환합니다. 이 접근 방식은 웹 브라우징 행동 및 공항 교통 흐름과 같은 모델링 시스템에 유용한 것으로 입증되었습니다. Benson은 이를 확장할 수 있는 다른 방법에 대한 아이디어를 가지고 있습니다. 그와 그의 동료들은 최근 기술 된 고차 Markov 체인을 텐서라고 하는 다른 도구와 결합하는 확률적 또는 무작위 프로세스를 위한 새로운 모델입니다. 그들은 궤적을 얼마나 잘 예측할 수 있는지 알아보기 위해 뉴욕시의 택시 승차 데이터 세트에 대해 테스트했습니다. 결과는 엇갈렸습니다. 그들의 모델은 일반적인 Markov 체인보다 운전실의 움직임을 더 잘 예측했지만 어느 모델도 그다지 신뢰할 수 없었습니다.

텐서 자체는 최근 몇 년 동안 자체적으로 등장한 고차 상호 작용을 연구하기 위한 또 다른 도구입니다. 텐서를 이해하려면 먼저 데이터를 행과 열의 배열로 구성하는 행렬을 생각하십시오. 이제 행렬로 구성된 행렬, 또는 행과 열뿐 아니라 깊이나 기타 차원의 데이터도 포함하는 행렬을 상상해 보십시오. 이들은 텐서입니다. 모든 매트릭스가 뮤지컬 듀엣에 해당한다면 텐서는 가능한 모든 악기 구성을 포함합니다.

텐서는 예를 들어 입자의 다양한 가능한 양자 상태를 설명하는 데 오랫동안 사용해 온 물리학자들에게 새로운 것이 아니지만 네트워크 이론가들은 고차원 데이터 세트에서 행렬의 힘을 확장하기 위해 이 도구를 채택했습니다. 그리고 수학자들은 그것들을 사용하여 새로운 종류의 문제를 풀고 있습니다. Grochow는 텐서를 사용하여 연구합니다. 동형 문제, 본질적으로 두 객체가 어떤 면에서 동일한지 여부를 어떻게 알 수 있는지 묻습니다. Youming Qiao와의 최근 작업은 새로운 방법 해결하기 어렵거나 불가능한 복잡한 문제를 식별합니다.

책임감 있게 하이퍼그래프를 작성하는 방법

Benson의 결정적이지 않은 택시 모델은 만연한 질문을 제기합니다. 연구자들은 하이퍼그래프와 같은 도구가 실제로 언제 필요합니까? 많은 경우에 적절한 조건에서 하이퍼그래프는 그래프와 정확히 동일한 유형의 예측 및 분석을 제공합니다. "무언가 네트워크에 이미 캡슐화되어 있는 경우 시스템을 [고차로] 모델링해야 합니까?" 물었다 마이클 샤웁 RWTH Aachen 대학의.

그는 데이터 세트에 따라 다르다고 말했다. “그래프는 소셜 네트워크에 대한 좋은 추상화이지만 소셜 네트워크는 그 이상입니다. 고차원 시스템을 사용하면 모델링할 수 있는 방법이 더 많아집니다.” 예를 들어, 그래프 이론은 개인이 어떻게 연결되어 있는지 보여줄 수 있지만 소셜 미디어의 친구 클러스터가 서로의 행동에 영향을 미치는 방식은 포착하지 못합니다.

모든 데이터 세트에서 동일한 고차 상호 작용이 나타나지는 않을 것이므로 새로운 이론은 흥미롭게도 데이터에 의해 주도됩니다. “제가 수학을 좋아하는 이유는 수학이 논리에 기반을 두고 있고 올바른 방향을 따르면 올바른 답을 얻을 수 있다는 것입니다. 그러나 때로는 완전히 새로운 수학 영역을 정의할 때 올바른 방법이 무엇인지에 대한 주관성이 있습니다.”라고 그녀는 말합니다. "그리고 여러 가지 방법이 있다는 것을 인식하지 못한다면 커뮤니티를 잘못된 방향으로 이끌 수 있습니다."

궁극적으로 이러한 도구는 연구자가 데이터를 더 잘 이해할 수 있게 해줄 뿐만 아니라 수학자와 컴퓨터 과학자가 새로운 가능성의 세계를 탐색할 수 있도록 하는 일종의 자유를 의미한다고 Grochow는 말했습니다. “탐구할 것이 끝이 없습니다. 흥미롭고 아름답고 많은 훌륭한 질문의 원천입니다.”